4.5. The Minimum Spanning Tree Problem

• A Spanning Tree is a tree that spans all the nodes in a graph
• Given a connected graph G = (V, E) with positive edge weights c_e, a Minimum Spanning Tree is a subset of the edges T ⊆ E such that T is a spanning tree whose sum of edge weights is minimized.

• We need to find the cheapest spanning tree of the graph, which is called the Minimum Spanning Tree as mentioned above

Three simple algorithms that efficiently finds the Minimum Spanning Tree:

• Start with some root node s and greedily grow a tree T from s outward
• At each step, add the cheapest edge e to T that has exactly one endpoint in T
• Similar to Dijkstra’s (but simpler)
• So, in brief:
  • Maintain a set S ⊆ V ,the set on which we have constructed the spanning tree so far
    
  • Initially S = {s}, s the root node
    
  • In each iteration:
    
  • Grow S by one node, adding to S a node v whose cost = min _{e = (u,v):u in S} C_e
    
  • Also add the edge e =(u,v) that satisfies the above formula.
    

Ø Start with T = φ Ø Consider edges in ascending order of cost Ø Insert edge e in T unless doing so would create a cycle • Reverse-Delete algorithm. Ø Start with T = E Ø Consider edges in descending order of cost Ø Delete edge e from T unless doing so would disconnect T