Algorithm
1. Each non-root picks cheapest incoming edge. 2. If result is tree → done. 3. Else contract cycles into supernodes. 4. Recurse.
Advertisement
Complexity
Naive O(VE). Tarjan's implementation: O(E log V). Gabow's O(E + V log V).
Advertisement
Why cycles form
Local minima can conflict. Cycle contraction resolves — original min-in-edges will be replaced by one bringing tree in from outside.
Applications
Parsing (dependency trees). Bit-torrent network design. Broadcast tree in directed networks.