Tuesday, January 3, 2012

Prim's and Kruskal's algorithms

 
MST-Kruskal(G,w)
01 A ¬ Æ
02 for each vertex v Î V[G] do
03    Make-Set(v)
04 sort the edges of E by non-decreasing weight w
05 for each edge (u,v) Î E, in order by non-decreasing weight do
06   if Find-Set(u) ¹ Find-Set(v) then
07      A ¬ A È {(u,v)}
08      Union(u,v)
09 return A


MST-Prim(G,w,r)
01 Q ¬ V[G]  // Q – vertices out of T
02 for each u Î Q
03    key[u] ¬ ¥
04 key[r] ¬ 0
05 p[r] ¬ NIL
06 while Q ¹ Æ do
07   u ¬ ExtractMin(Q)  // making u part of T
08      for each v Î Adj[u] do
09         if v Î Q and w(u,v) < key[v] then
10            p[v] ¬ u
11            key[v] ¬ w(u,v) 
 
















0 comments: