Minimum Spanning Tree algorithms:

 

Kruskal's algorithm

MST-KRUSKAL (G = (V,E), w)

 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 */

 

FIND_SET (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

 

Prim's algorithm

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

Cheriton-Tarjan's algorithm

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 T1 Ü Q     /* Let T1 be the tree in front of Q */
 8.                 if stage(T1) = j
 9.                    do j:=j+1
 10.                       CLEAN-UP
 11.               find edge (u,v)Î E with min weight such that u ÎT1 , v ÎV-T1
 12.               let T2 be the tree in Q that contains v
 13.               T:= MERGE(T1,T2    /* by adding edge (u,v)  to MST*/
 14.               Q:=Q-T1-T2        /* Remove T1 & T2 from Q */
 15.               stage(T):= 1+min { stage(T1), stage(T2) } 
 
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