1.10.3 spanning tree

• BFS and DFS will produce spanning tree.
• The minimum spanning tree can be obtained in polynomial time:
  1. Kruskal’s algorithm
  2. Prim’s algorithm
  3. Sollin’s algorithm
• Kruskal algorithm:
  KRUSKAL(G): 
   A = empty 
   foreach v in G.V: 
      MAKE-SET(v) 
   foreach (u, v) ordered by weight(u, v), increasing: 
      if FIND-SET(u) âĽă FIND-SET(v): 
         A = A  {(u, v)} 
         UNION(u, v) 
   return A