Algorithms For Dummies

Testing Kruskal’s algorithm

Kruskal’s algorithm uses a greedy strategy, just as Prim’s does, but it picks the 

shortest edges from a global pool containing all the edges (whereas Prim’s evalu-

ates the edges according to the vertexes in the spanning tree). To determine 

whether an edge is a suitable part of the solution, the algorithm relies on an 

aggregative process in which it gathers vertexes together. When an edge involves 

vertexes already in the solution, the algorithm discards it to avoid creating a cycle. 

The algorithm proceeds in the following fashion:

1. 

Put all the edges into a heap and sort them so that the shortest edges are on top.

2. 

Create a set of trees, each one containing only one vertex (so that the number 

of trees is the same number as the vertexes). You connect trees as an aggre-

gate until the trees converge into a unique tree of minimal length that spans all 

the vertexes.

3. 

Repeat the following operations until the solution doesn’t contain as many 

edges as the number of vertexes in the graph: