Minimum Spanning Tree algorithms:

• Kruskal

• Prim

• Cheriton-Tarjan

 1.  A := Æ       /*A Set of edges in minimum spanning tree*/
 2.  for each vertex v Î V[G]
 3.      do MAKE-SET(v)
 4.  sort the edges of E into nondecreasing order by weight w
 5.  for each edge (u,v) Î E, taken in nondecreasing order by weight
 6.           do if  FIND-SET(u) ¹ FIND-SET(v)
 7.               then A := A U {(u,v)}
 8.                        UNION( u,v )
 9.  return A

END

MAKE-SET(v)

 1.  p[v] := v            /* p[v] is parent of node v */
 2.  rank[v] := 0       /* rank[v] is upperbound on height of node v */

 1.  if  v ¹ p[v]        /* determine whether v is the root if so go to line 2*/
 2.      then  p[v]:= FIND-SET(p[v])
 3.  return  p[v]

UNION ( u ,v)

 1.  LINK ( FIND-SET(u) , FIND-SET(v) )
 

LINK ( u ,v)

 1.  if  rank[u] > rank[v]       
 2.      then  p[v] := u
 3.      else  p[u] := v
 4.               if rank[u]=rank [v] 
 5.                  then rank[v] := rank [v] +1           

                                                                                                                                                                        Go Back to Top

MST-PRIM (G = (V,E), w, Source s)

 1.  for each vertex u in V[G]
 2.        do key[u] := ¥
 3.             p[u] := NIL         /*p[u] ia parent of node u */
 4.  key[s] := 0
 5.  Q := V[G]    /*Q is a priority queue of set of all vertices not in the tree */
 6.   while Q ¹ {}      
 7.            do u:= EXTRACT-MIN(Q)
 8.                 for each v Î Adj[u]
 9.                       do if v Î Q and w(u,v) < key[v]
 10.                              then p[v] := u
 11.                                     key[v] := w(u,v)

END

                                                                                                                                                                                                                                Go Back to Top

MST-CHERITON-TARJAN (G = (V,E), w)

 1.  Q := Æ      /*A Set of edges in minimum spanning tree*/
 2.  for each vertex v Î V[G]
 3.      do Q Ü v
 4.              stage(v) := 0 
 5.  j := 1      /* j is stage number which is initialized to 1 */
 6.  while |Q| ³ 2
 7.           do T₁ Ü Q     /* Let T₁ be the tree in front of Q */
 8.                 if stage(T₁) = j
 9.                    do j:=j+1
 10.                       CLEAN-UP
 11.               find edge (u,v)Î E with min weight such that u ÎT₁ , v ÎV-T₁
 12.               let T₂ be the tree in Q that contains v
 13.               T:= MERGE(T₁,T₂)      /* by adding edge (u,v)  to MST*/
 14.               Q:=Q-T₁-T₂        /* Remove T₁ & T₂ from Q */
 15.               stage(T):= 1+min { stage(T₁), stage(T₂) } 
 16.               Q<==T

END

ClEAN-UP

Shrink G to G^* where  G^* is G with each tree shrunk to a single node and only those edges (u,v) ΠG^*, u Î T, vÎ T^', that are shortest incident edges between disjoint T, T^'.

                                                                                                                                                                                                                            Go Back to Top