Published
- 1 min read
Kruskal algorithm to construct minimum spanning tree in an undirected graph
Kruskal Algorithm
Kruskal algorithm is to construct minimum spanning tree from an undirected graph. As its a tree there shouldnt be any cycles in that tree Following diagram shows the empty and connected edges based on their weight using kruskal algorithm with conditions
Conditions for Kruskal Algorithm
- Ascending order sorting of the edges
- Start choosing edges based on above output, to form minimum spanning tree, skip the edges that produce cycles
- Repeat step 2 until the n-1 edges are formed
Why does Kruskal Algorithm chooses only n-1 edges ?
Using more than n-1 edges will form a cycle