Chu-Liu/Edmonds algorithm

Finds the maximum spanning arborescence in a directed graph by recursively resolving cycles.

Independently published by Chu and Liu (1965) and Edmonds (1967), this algorithm identifies the optimal spanning arborescence within a directed graph. The process involves two main steps: greedily selecting the highest-weight incoming edge for each node and recursively contracting cycles into super-nodes until a root is established. With an optimized runtime of O(E + V log V), it remains a foundational tool for dependency parsing (mapping syntactic structures in linguistics) and complex network design.

https://en.wikipedia.org/wiki/Edmonds%27s_algorithm