Chu-Liu-Edmonds
Same as directed MST algorithm. Each vertex picks cheapest in-edge. Contract cycles + recurse.
Advertisement
Complexity
O(VE) naive, O(E log V) Tarjan, O(E + V log V) Gabow.
Advertisement
Applications
Dependency parsing (natural language). Broadcasting in directed networks. Cheapest way to reach every node from root.
Difference from MST
Undirected MST: symmetric, easy. Directed: cheapest in-edges can conflict via cycles → need contraction.