寻找所有最小生成树。

Question

6

可能重复：
所有最小生成树实现

如何以高效的方式在无向图中找到所有最小生成树？

- user182513

1

请注意，最小生成树的数量可能与图的大小呈指数关系，因此您可能不想返回它们全部。 - Keith Randall

1

@keith Knuth写了一本关于在图中枚举树的书。仅仅因为你有指数级别的东西，并不意味着你不想看到它们全部。在这种情况下，这只是意味着对于一个一般的大图来说，看到它们全部并不实际。 - David Nehme

3个回答

0

是的，有算法可以生成图中所有生成树。至少其中一个通过仅生成树之间的差异来压缩输出。正如其他人指出的那样，即使对于小图形也可能有很多最小生成树。

- David Nehme

-1

你可以找一个修改 BFS 算法的例子！

- madCode

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dervin Thunk · Accepted Answer

很抱歉回答有些学术化... 但是Knuth在TAOCP第4卷的第4部分的算法S恰好关于生成所有生成树（第26页以下）。他在谈论生成（生成）树时有一些musings，但在TAOCP中可以找到最好的参考。