algorithm - 使用 Kruskal 算法查找图的最小生成树

Question

Here is a Graph我需要使用 Prim 的 和 Kruskal 的 算法找到 G 的最小生成树。

我使用 Prim 算法找到了最小生成树。 Here is my attempt .

我在使用 Kruskal 算法找到最小生成树时遇到困难。我看过很多与 Kruskal 图算法相关的视频，但我最终得到的图与 Prim 算法相同。

谁能告诉我如何使用 Kruskal 算法找到图的最小生成树？

Answer 1

Prims and Kruskals will always give you the same answer if all the edges of the graph have distinct weights, as there is only a single min-spanning tree that exists. For graph having many edges with same weights, the algorithms could give you a different answer but not always. Depends on the way the nodes are explored in the implementation. This graph can have many different min-spanning trees.

由于您的图表具有所有不同的边权重，因此您总是会得到相同的答案。