Finding the minimum spanning tree of a graph using Kruskal's Algorithm

0
votes

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

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

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?

2
algorithmdata-structuresgraphkruskals-algorithmprims-algorithm
Why do you think they should produce different results? – Nico Schertler
@NicoSchertler Because, these are two different algorithms – philip
Looks like all the edges in the graph have distinct weights. That means that there is only one minimum spanning tree. Any algorithm you use to find it should find the same one. – Matt Timmermans
@MattTimmermans So, by using either Prim's or Kruskal's algorithm, do we get the same result for this graph? – philip

2 Answers

1
votes

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.

0
votes

Prim's and Kruskal's algorithm both find minimum spanning trees. Because the graph that you gave has edge weights that are all different from each other there will be no different spanning trees that are both minimum.as long as both algorithms are correctly implemented they will find the same tree. meaning there can be no variation between the MST.