使用Kruskal算法找到图的最小生成树

本文介绍了使用Kruskal算法找到图的最小生成树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这里是一个图，我需要在其中找到G的最小生成树使用 Prim的和 Kruskal的算法。

Here is a Graph where I need to find the minimum spanning tree of G using Prim's and Kruskal's algorithms.

我使用Prim的算法找到了最小生成树。 这是我的尝试。

I found the minimum spanning tree using Prim's algorithm. Here is my attempt.

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

I am having difficulty in finding the minimum spanning tree using Kruskal's algorithm. I have seen many videos related to Kruskal's graph algorithm but I ended up getting the same graph as Prim's algorithm.

有人可以告诉我如何找到最小的生成树吗？

Can anyone please show me how to find the minimum spanning tree of the graph using Kruskal's algorithm?

推荐答案

Prims和Kruskals总是会给您相同的答案图的边具有不同的权重，因为仅存在一个最小跨度的树。对于具有许多具有相同权重的边的图，算法可以为您提供不同的答案，但并非总是。取决于实现中探索节点的方式。此图可以包含许多不同的最小生成树。

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.

由于您的图具有所有不同的边缘权重，因此您将始终获得相同的答案

As your graph has all distinct edge weights, you will always get the same answer.