mst

Minimum Spanning Tree

Solution

• Grow a spanning tree by finding the edges that are safe iteratively.
  • A cut
  • An edge crosses the cut
  • An light edge crossing the cut
  • safe edge = adding this edge to $A$ maintains the property that $A\subseteq T$, e.g. no cycle, low weight.
  • When the algorithm is running $G_A$ will be a forest, in which each connected component is a tree. As the algorithm runs, light edges crossing each connected components are picked to form the spanning tree.

def MST(G, w)
    A = set()  # some set
    while A is not spanning tree:
        find an edge (u, v) that is safe for A
        A.add( (u, v) )
    return A

• Based on the generic method, algorithms of Kruskal and Prim each uses a specific rule to determine a safe edge.
  • Kruskal: $A$ is a forest with all vertices, safe edge is a lowest-weight edge in the graph that connects two distinct components.
  • Prim: $A$ is a single tree, safe edge is a lowest-weight edge connecting the tree to a vertex not in the tree.
  • Both takes $O(E\lg V)$ time (using bin-heap for Prim)