Skip to content

Minimum Spanning Tree

Summarized notes on Introduction to Algorithms, Chapter 23

  • tree - is an undirected graph with no cycles, i.e. connected graph with \(N\) nodes and \(N-1\) edges
  • spanning tree - acyclic subset \(T \in E\) that connects all vertices
  • minimum-spanning tree problem - process of determining \(T\)
  • greedy algorithm - perform locally optimal choices → solution not guaranteed to be globally optimal

Growing a Minimum Spanning Tree

Generic algorithm that grows the MST one edge at a time - manages a set od edges \(A\) maintaining the following loop invariant:

prior to each iteration, \(A\) is a subset of some minimum spanning tree - at each step, determine safe edge \((u, v)\) that can be added to \(A\) without violating this invariant - algorithm terminates as soon as \(A\) forms a MST

Finding a safe edge

  • looking for \((u, v) \in T\) such that \((u, v) \notin A\) → one must exist since \(A \in T\)
  • cut \((S, V - S)\) of undirected graph \(G = (V, E)\) is a partition of \(V\)
  • edge crosses the cut if one endpoint is in \(S\) and other is in \(V-S\)
  • cut respects edges of \(A\) if no edge in \(A\) crosses the cut
  • light edge is the minimum weight edge crossing a cut → multiple may exist
  • \(A\) is always acyclic
  • asymptotic time not given, but \(|V| - 1\) iterations over edges → \(\Omega(V + E)\)

Theorem for identifying safe edge

Let \(G=(V, E)\) be connected, undirected graph with real-valued weight function \(w\) defined on \(E\). Let \(A\) be a subset of \(E\) that is included in some minimum spanning tree for \(G\), left \((S, S-V)\) be any cut of \(G\) that respects \(A\), and let \((u, v)\) be a light edge crossing \((S, V-S)\). Then edge \((u, v)\) is safe for \(A\).