这里是一个图,我需要在其中找到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算法找到图的最小生成树
发布评论