Minimum Spanning Arborescence — Directed Version of MST

Why it matters

Directed spanning tree with min cost appears in network design + parsing. Understanding shapes directed graph optimization.

The architecture

For each non-root vertex: pick min incoming edge.

If no cycle: done.

If cycle: contract, recurse.

How it works end to end

Complexity: O(VE) naive; O(E + V log V) with better data structures.

Applications: dependency parsing (NLP), network broadcast tree.