令 G = (V, E) 为加权、连通且无向图。描述一个有效的算法，它决定 G 中是否正好有 2 个不同的 MST。
我已经解决的上一个问题要容易得多：描述一种有效的算法来确定 G 中是否正好有一个 MST。
这就是我解决后一个问题的方法：
我们运行 Kruskal 算法，然后将新 MST 的边缘涂成蓝色，其余边缘涂成红色。
然后我使用了另一种我们见过的简单算法（使用 Kruskal），它在包含最大数量红色边的图形中找到一个 MST——这意味着它是图形 G 中的一个 MST，而不管边的颜色如何，并且每隔一个 MST 不能包含比算法找到的 MST 更多的红色边缘。
现在只有一个 MST，如果算法找到相同的 MST（包含所有蓝色边缘）。
这里的另一个问题似乎要复杂得多。我尝试过使用上述算法，也尝试过使用其他各种技巧，但都没有奏效。
顺便说一句，我听说有一种算法可以计算图中不同 MST 的数量，但这确实是一种矫枉过正——我被要求提供一个简单的算法。
我会很感激任何帮助，谢谢
我可能正在考虑它，但你的方法似乎不必要地复杂。为了确定是否有 2 个不同的 MST，我首先运行 Kruskal 以获取第一个 MST。然后你再次运行它，看看你是否可以避免从第一个 MST 中获得优势。
在 Kruskal 的每个步骤中，您添加连接 2 个以前未连接的组件的最便宜的边。因此，您必须按重量对边缘进行排序并遍历它们，如果它们连接了 2 个未连接的组件，则将它们添加到 MST。当有多个 MST 时，您将达到一个点，您可以在两个连接相同组件的相同权重的边之间进行选择。
运行 Kruskal 一次后，您就知道 MST 中有哪些边。如果您再次运行它，您将再次按权重对边进行排序，并将最便宜的边（连接 2 个未连接的组件）添加到您的图表中。但是，如果您可以选择添加 2 条连接相同组件的边，那么您可以采用第一次没有采用的边。最终结果将是一个不同的 MST（不包含一个边），但是一个有效的 MST，因为您完全按照 Kruskal 的规则进行操作。
您基本上只是做 Kruskal，但将您的平局断路器更改为具有相同重量的边缘。重复该过程以找到更多不同的 MST。如果您想知道是否只有 2 个 MST，您应该尝试找到第三个 MST。