algorithm - 我应该如何检查我的图表是否至少有 X 个最小生成树？

Question

我正在寻找一种有效的算法来查找图表中是否存在至少“X”个 MST。任何指针？

Answer 1

这并没有充实完整的算法，而是对An algorithm 的公认答案，以查看图中是否恰好有两个 MST？（@j_random_hacker）提出了一个可能对你有很大帮助的观点。摘自他的回答：

此外，每个MST 都可以通过选择某种特定的方式来对每组等权边进行排序，然后运行 ​​Kruskal 算法来生成。

您可能会编写一个算法来利用这一点来获取 MST 的数量。好吧，只是直接使用这个事实，没有别的可能不会进入“高效算法”领域，尽管我认为任何有效的算法都会利用几个类似的事实。如果我找到任何结果，我会添加更多结果。