Kruskal’s Algorithm is almost similar to Prim’s Algorithm. The difference is that in Prim’s algorithm, the root node chosen is the one having minimum weight but in Kruskal’s algorithm the root vertex is chosen randomly provided the edges are arranged in the ascending order. Here are few steps to follow in finding Minimum Spanning Tree (MST). We shall use the same example from Prim’s.

Step 1: Arrange the edges in ascending order as shown in Fig 1.2.

Step 2: From the given graph, remove all loops and parallel edges. The one with the maximum weight of the parallel edges should be removed. According to Fig 1.1, remove the loop around F and the parallel edge of BD that has maximum weight 8. That gives the below i.e. Fig 1.3

Step 3: Choose first node from the ascending order. So, let us choose E->F from Fig 1.3. We can choose E->D as well. That doesn’t change the final result.

Step 4: From the root node E, select the path to which the edge weight is minimum out of the remaining connected nodes to the root. Here minimum weight is 2 compared to E->C which is 3. We are free to choose E->F or E->D. We choose here E->F.

Step 5: Considering F as a node, apply step 3. Now we have to consider the weights of the edges from the previous vertices i.e E in this case. Since E->D edge has minimum weight i.e 2 out of 3 (E->C) and 5 (F->D), we choose E->D.

Step 6: Repeat steps 4 and 5 until all the vertices are connected according to the ascending order.

• 

• 

• <img src="https://techprodezza.code.blog/wp-content/uploads/2020/07/8.jpg?w=861&quot; alt="Fig. 1.8
  

Step 7: Exit.

In Fig. 1.8 we connected B->A as B->D forms a cycle, which is not acceptable. And also ignored D->F, A->C since they form a cycle.

Note : The resulting MST should not form a cycle with any of the vertices.

From Prim’s and Kruskal’s Algorithm, it is proved that Minimum Spanning Tree is same for any graph and hence only single optimal solution.

Prim’s Algorithm	Kruskal’s Algorithm
It starts to build MST from any arbitrary vertex. To be more precise with Greedy Algorithm, choose the one with minimum weight.	It starts to build MST from the first vertex when arranged in ascending order. (Priority Queue)
It is based on Greedy Algorithm.	It is also based on Greedy Algorithm.
These run faster in Dense graphs.	These run faster in Sparse graphs.

Comment for any discrepancies or queries or suggestions. Stay updated for more!

References and Recommendations:

• Greedy method
• Prim’s Algorithm
• Huffman’s Encoding
• Dijkstra’s Algorithm