This is an old revision of the document!
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
