Kruskal's Algorithm

Wednesday, 24 April 2019

10:25 AM

Kruskal's algorithm is a minimum-spanning-tree algorithm which takes a weighted graph and returns a spanning-tree whose total weight (the sum of all the weights) is not larger than any other spanning tree.

 

For a weight graph with  vertices Kruskal's algorithm is:

 

    Sort the edges by weight (edges of equal weight can be considered in any order),

    Go over the sorted edges and include them unless the choice would form a cycle,

    Repeat step 2 until no edges remain (or until  edges have been selected).