algorithm - 如何在图中找到最小生成树的数量？使用克鲁斯卡尔算法

Question

我正在尝试使用 kruskal 算法在图中找到所有最小生成树。

我知道，如果所有边的权重彼此不同，则图中将只有一棵最小生成树。因此，对于图中两个以上的最小生成树，必须至少有两条边具有相同的权重。因此，我想我应该开始用相同的重量切割边缘。

但是，我想知道如果我一次切割不同数量的边缘会有所不同吗？

谢谢！！

Answer 1

如果您的图表具有相同权重的不同边，那么您将可以选择首先切割哪条边，无论您选择先切割哪条边，仍然会给您一个最小生成树，但是以不同的顺序切割可能会给您不同的最小值生成树（尽管它们的总重量仍然相同）。

但是，我想知道如果我一次切割不同数量的边缘会有所不同吗？

你没有道理，你一次只能用 Kruskall 削减一个优势。