This is an old revision of the document!
Table of Contents
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 ce, 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.
Problem To be solved
- We need to find the cheapest spanning tree of the graph, which is called the Minimum Spanning Tree as mentioned above
Designing the algorithm
Three simple algorithms that efficiently finds the Minimum Spanning Tree:
Prim's algorithm
- 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 Ce
- Also add the edge e =(u,v) that satisfies the above formula.
Kruskal's algorithm
- 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
Reverse-Delete algorithm
- 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
Analyzing the Algorithms
- The Cut Property :
- Assume all edge costs are distinct
- 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
