joshita / dev

Published

- 1 min read

Kruskal algorithm to construct minimum spanning tree in an undirected graph

img of 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

TotalValue TotalValue TotalValue

Conditions for Kruskal Algorithm

  1. Ascending order sorting of the edges
  2. Start choosing edges based on above output, to form minimum spanning tree, skip the edges that produce cycles
  3. Repeat step 2 until the n-1 edges are formed

Why does Kruskal Algorithm chooses only n-1 edges ?

TotalValue

Using more than n-1 edges will form a cycle