Generic-MST(G,w)
1 A = empty
2 while A does not form a spanning tree
3 do find an edge (u,v) that is safe for A
4 A = A union {(u,v)}
5 return A
MST-Kruskal(G,w)
1 A = empty
2 for each vertex v in V[G]
3 do Make-set(v)
4 sort the edges of E by nondecreasing weight w
5 for each edge (u,v) in E, in order by nondecreasing weight
6 do if Find-set(u) != Find-set(v)
7 then A = A union {(u,v)}
8
Union(u,v)
9 return A
The running time of Kruskal depends on the implementation of the disjoint-set data structure. Assume the disjoint set with the union-by-rank and path-compression heuristics. The total running time is O(E lg E)
MST-Prim(G,w,r)
1 Q = V[G]
2 for each u in Q
3 do key[u] = inf
4 key[r] = 0
5 pi[r] = NIL
6 while Q != empty
7 do u = Extract-min(Q)
8 for each v in Adj[u]
9 do if u in Q and w(u,v) <
key[v]
10
then pi[v] = u
11
key[v] = w(u,v)
The key to efficient implementation of Prim is to make it easy to select
a new edge to be added to the tree formed by the edges in A. Q is
a priority queue based on key field. During the algorithm,
the set A from Generic-MST is kept implicitly as
A = {(v, pi[v]) | v in V - {r} - Q }
When the algorithm terminates, the priority Q is empty, the minimum
spanning tree A for G is thus
A = {( v, pi[v] ) | v in V - {r} }.
The total running time for Prim's algorithm is O( E lg V ). The
asymptotic running time can be improved by using Fibonacci heaps to implement
the priority queue. If |V| elements are organized into a Fibonacci
heap, Extract-min operation in O(lg V) amortized time and Decrease-key
operation in O(1) amortized time. The running time is O(E + V lg
V ).