图的所有生成树的枚举算法

Question

有什么简单的方法来枚举无向图的所有生成树吗？这可能具有O(2^n)复杂性。图上的节点数总是小于10。我知道Knuth在TAoCP的第4卷上有一个算法，但我找不到它。

Answer 1

文献中还有其他的作品，你查过了吗？首先给出了Char算法，在[Jayakumar等人‘84年]中进行了描述。还有[Kapoor & Ramesh'91]算法，在他们的文章中有详细描述，还有[波兹尼科夫‘94]的工作。

另外，您可能会看到另一个步骤：求有向加权图的所有生成树 (一些答案提到无向图)。

最后，请注意，即使算法复杂度很高，这在实践中可能不是一个问题，在这样一个小图上。