Analysis of Algorithms : An Active Learning Approach

6.4 MINIMUM SPANNING TREE ALGORITHM 161

The general algorithm that will accomplish this is (where E represents the
number of edges and N the number of vertices)
sort the edges in nondecreasing order by weight
initialize partition structure
edgeCount = 1
includedCount = 0
while edgeCount ≤ E and includedCount ≤ N-1 do
parent1 = FindRoot( edge[edgeCount].start )
parent2 = FindRoot( edge[edgeCount].end )
if parent1 ≠ parent2 then
add edge[edgeCount] to spanning tree
includedCount = includedCount + 1
Union( parent1, parent2 )
end if
edgeCount = edgeCount + 1
end while

Our main loop will continue until the edgeCount variable indicates that
we have looked at all of the edges or the includedCount indicates that we
have added enough edges to create the spanning tree. You should see that if we
have N nodes in the graph, a spanning tree would have one less edge than
nodes.
Inside the loop, we first find the parents of the two nodes that are connected
by the next edge we are considering. If those nodes are in partitions with dif-
ferent roots, adding an edge between them will not create a cycle, so this cur-
rent edge can be added to the MST and those two pieces can be joined so that
they now have the same root. The details of the FindRoot and Union rou-
tines will be given in Section 6.7.
The complexity of this algorithm will be the complexity of the sort algo-
rithm used because the while loop is linearly related to the number of edges.
This makes the complexity of Kruskal’s MST algorithm O(E lg E).