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) )

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

# 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

# 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'.