使用Kruskal算法找到图的最小生成树 [英] Finding the minimum spanning tree of a graph using Kruskal's Algorithm

问题描述

这里是一个图，我需要在其中找到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.

这篇关于使用Kruskal算法找到图的最小生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！