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 = φ,thus T = an empty tree
• Consider edges in ascending order of cost
• Insert edge e in T as long as e doesn't create a cycle when added
• if e creates a cycle, we ignore it and move on to the next node

• Start with T = E, E the set of all the nodes in the graph
• Consider edges in descending order of cost
• Delete edge e from T unless doing so would disconnect T

• The Cut Property :
  • Assume all edge costs are distinct –> The MST is unique
  • Now, let S be any subset of nodes that is neither empty nor equal to V
  • And let edge e = (v,w) be the minimum cost edge with one end in S and the other in V-S
  • Then an spanning tree contains the edge e
  • This straight-out-of-the-book statement is the cut property of the Minimum Spanning Tree.Proof:See book
  • So, we can insert nodes in the MST as long as we don't create cycle when doing so.
• Prim's and Kruskal's algorithms produce a Minimum spanning tree of the graph G
  
• The Cycle property:
  • Let C be any cycle, and let f be the maximum cost edge belonging to C
  • Then MST does not contain f.
  • So, we can delete a node from the MST as long as we don't disconnect our MST
• The Reverse-Delete Algorithm produces a Minimum Spanning Tree of the graph G

• We need to decide which node v to add next to the set S at each time
• We maintain the attachment costs a(v) = min _{e = (u,v):u in S} C_e for each node v in V-S
• Keep the nodes in a Priority Queue(PQ) with a(v), the attachment costs, as the keys
• We use ExtractMin to extract the node v to add to S
• We use the ChangeKey operation to update the attachment costs
• The ExtractMin operation is performed n-1 times
• The ChangeKey operation is done at most once for each edge
• Thus using a PQ, we can implement Prim's algorithm in O(mlogn) time
  

Implementation from our class' lecture:

for each (v ∈ V) a[v] = ∞
Initialize an empty priority queue Q
for each (v ∈ V) insert v onto Q
Initialize set of explored nodes S = φ
while (Q is not empty)

u = delete min element from Q
S = S ∪ { u }
for each (edge e = (u, v) incident to u)

if (v ∉ S) and (c_e < a[v])

decrease priority a[v] to c_e

There are several applications of the Minimum Spanning Tree algorithms, many can be found in the book.
This was by far the most interesting reading of the chapter!I give it a 9/10.