Chu-Liu/Edmonds Algorithm

A Bit of History

The result is known by several names: Chu–Liu/Edmonds, Edmonds’ branching algorithm, or the directed minimum spanning tree algorithm. “Arborescence” is the most precise description of its output.

What Are We Building?

Given a directed weighted graph $G=(V,E)$ and root $r$, an outward rooted arborescence contains exactly $V-1$ edges, gives every $v\neq r$ exactly one incoming edge, gives $r$ none, and makes every vertex reachable from $r$. The goal is to minimize total edge weight.

Algorithm Overview

1. Check candidates. For every non-root vertex $v$, choose its minimum-weight incoming edge $p(v)\to v$. If any such vertex has none, no rooted arborescence exists.
2. Look for directed cycles. Following chosen parent edges either reaches the root or repeats a vertex. If no cycle exists, the chosen edges already form the optimum.
3. Contract every cycle. Replace each selected cycle by a super-vertex and assign component IDs to vertices outside cycles.
4. Reweight crossing edges. For an edge $u\to v$ whose endpoints contract to different components, use $w'(u,v)=w(u,v)-w(p(v),v)$.
5. Solve and expand. Repeat on the smaller graph. To reconstruct edges, expand contractions in reverse order and break each cycle where the chosen external edge enters.

Why the Greedy Edges Can Form a Cycle

Choosing the cheapest incoming edge is unavoidable locally: every non-root vertex needs one parent. But those individually cheapest choices can point around a directed loop. A loop satisfies indegree one for its members while failing the root-reachability requirement.

Contraction and the Meaning of Reweighting

Suppose an outside edge $u\to v$ enters cycle $C$. To use it, the final arborescence keeps the chosen cycle edges except $p(v)\to v$, which must be removed to break the cycle. The true extra cost of entering at $v$ is therefore:

original entry costminus displaced cycle edgeequals marginal entry cost

Edges leaving the cycle simply leave the super-vertex. For the iterative cost algorithm, every crossing edge is uniformly written as $w'(u,v)=w(u,v)-\operatorname{in}[v]$ after the selected incoming costs have been added to the answer.

Visual Walkthrough: Contract, Solve, Expand

Reconstructing the Actual Edges

The simple iterative implementation can return the optimum cost without retaining the arborescence itself. To recover edges, record a contraction frame containing the chosen incoming edge for every old vertex, the component mapping, and—most importantly—the original edge represented by every new crossing edge.

1. Store frames while contracting, including nested cycles.
2. Solve the smallest acyclic instance.
3. Expand frames in reverse order.
4. If a selected contracted edge enters a cycle through original vertex $v$, restore that external edge, omit the cycle-selected edge $p(v)\to v$, and keep all other selected edges in the cycle.

That provenance bookkeeping—not the optimal-cost recurrence—is the most error-prone part of production implementations.

Correctness Intuition

If the cheapest-incoming selection is acyclic, it is feasible and no arborescence can improve any vertex’s incoming choice independently, so it is optimal. If it contains a cycle $C$, every feasible rooted arborescence must enter $C$ from outside at least once. Given one chosen entry at $v$, keeping all other cheapest cycle edges is optimal inside $C$; only $p(v)\to v$ must be removed. Reweighting records exactly that exchange cost, establishing a cost-preserving correspondence between solutions before and after contraction. Repeating the argument proves correctness inductively.

Implementation

These complete $O(VE)$ listings compute the minimum total cost. They support negative weights and parallel edges, ignore self-loops, and return no result when the chosen root cannot span the graph. They do not reconstruct the edge set; use the contraction-frame method above when parent edges are required.

from math import inf

def directed_mst_cost(n, edges, root):
    """Return minimum rooted arborescence cost, or None if infeasible."""
    if not 0 <= root < n:
        raise ValueError("root is outside the graph")

    total = 0
    while True:
        # Cheapest incoming edge for every current non-root vertex.
        incoming = [inf] * n
        parent = [-1] * n
        for u, v, weight in edges:
            if u != v and v != root and weight < incoming[v]:
                incoming[v] = weight
                parent[v] = u
        incoming[root] = 0

        if any(weight == inf for weight in incoming):
            return None
        total += sum(incoming)

        # Find cycles in the chosen-parent graph.
        component = [-1] * n
        seen_from = [-1] * n
        cycle_count = 0
        for start in range(n):
            v = start
            while seen_from[v] != start and component[v] == -1 and v != root:
                seen_from[v] = start
                v = parent[v]
            if v != root and component[v] == -1:
                u = parent[v]
                while u != v:
                    component[u] = cycle_count
                    u = parent[u]
                component[v] = cycle_count
                cycle_count += 1

        if cycle_count == 0:
            return total

        # Non-cycle vertices become singleton components.
        next_component = cycle_count
        for v in range(n):
            if component[v] == -1:
                component[v] = next_component
                next_component += 1

        contracted = []
        for u, v, weight in edges:
            cu, cv = component[u], component[v]
            if cu != cv:
                contracted.append((cu, cv, weight - incoming[v]))

        root = component[root]
        n = next_component
        edges = contracted

edges = [(0,1,4), (0,2,8), (1,2,2), (2,1,1),
         (1,3,5), (2,3,3)]
print(directed_mst_cost(4, edges, 0))  # 9

#include <iostream>
#include <limits>
#include <optional>
#include <utility>
#include <vector>
using namespace std;

struct Edge { int from, to; long long weight; };

optional<long long> directedMstCost(int n, int root, vector<Edge> edges) {
    const long long INF = numeric_limits<long long>::max() / 4;
    long long total = 0;

    while (true) {
        vector<long long> incoming(n, INF);
        vector<int> parent(n, -1);
        for (const Edge& e : edges) {
            if (e.from != e.to && e.to != root && e.weight < incoming[e.to]) {
                incoming[e.to] = e.weight;
                parent[e.to] = e.from;
            }
        }
        incoming[root] = 0;
        for (long long w : incoming) if (w == INF) return nullopt;
        for (long long w : incoming) total += w;

        vector<int> component(n, -1), seenFrom(n, -1);
        int cycleCount = 0;
        for (int start = 0; start < n; ++start) {
            int v = start;
            while (seenFrom[v] != start && component[v] == -1 && v != root) {
                seenFrom[v] = start;
                v = parent[v];
            }
            if (v != root && component[v] == -1) {
                for (int u = parent[v]; u != v; u = parent[u])
                    component[u] = cycleCount;
                component[v] = cycleCount++;
            }
        }
        if (cycleCount == 0) return total;

        int nextComponent = cycleCount;
        for (int v = 0; v < n; ++v)
            if (component[v] == -1) component[v] = nextComponent++;

        vector<Edge> contracted;
        for (const Edge& e : edges) {
            int a = component[e.from], b = component[e.to];
            if (a != b) contracted.push_back({a, b, e.weight - incoming[e.to]});
        }
        root = component[root];
        n = nextComponent;
        edges = move(contracted);
    }
}

int main() {
    vector<Edge> edges = {
        {0,1,4}, {0,2,8}, {1,2,2},
        {2,1,1}, {1,3,5}, {2,3,3}
    };
    auto answer = directedMstCost(4, 0, edges);
    if (answer) cout << *answer << '\n';  // 9
}

import java.util.*;

class ChuLiuEdmonds {
    static class Edge {
        int from, to;
        long weight;
        Edge(int from, int to, long weight) {
            this.from = from; this.to = to; this.weight = weight;
        }
    }

    static OptionalLong directedMstCost(int n, int root, List<Edge> edges) {
        final long INF = Long.MAX_VALUE / 4;
        long total = 0;

        while (true) {
            long[] incoming = new long[n];
            int[] parent = new int[n];
            Arrays.fill(incoming, INF);
            Arrays.fill(parent, -1);
            for (Edge e : edges) {
                if (e.from != e.to && e.to != root && e.weight < incoming[e.to]) {
                    incoming[e.to] = e.weight;
                    parent[e.to] = e.from;
                }
            }
            incoming[root] = 0;
            for (long w : incoming) if (w == INF) return OptionalLong.empty();
            for (long w : incoming) total += w;

            int[] component = new int[n];
            int[] seenFrom = new int[n];
            Arrays.fill(component, -1);
            Arrays.fill(seenFrom, -1);
            int cycleCount = 0;

            for (int start = 0; start < n; start++) {
                int v = start;
                while (seenFrom[v] != start && component[v] == -1 && v != root) {
                    seenFrom[v] = start;
                    v = parent[v];
                }
                if (v != root && component[v] == -1) {
                    for (int u = parent[v]; u != v; u = parent[u])
                        component[u] = cycleCount;
                    component[v] = cycleCount++;
                }
            }
            if (cycleCount == 0) return OptionalLong.of(total);

            int nextComponent = cycleCount;
            for (int v = 0; v < n; v++)
                if (component[v] == -1) component[v] = nextComponent++;

            List<Edge> contracted = new ArrayList<>();
            for (Edge e : edges) {
                int a = component[e.from], b = component[e.to];
                if (a != b) contracted.add(new Edge(a, b, e.weight - incoming[e.to]));
            }
            root = component[root];
            n = nextComponent;
            edges = contracted;
        }
    }

    public static void main(String[] args) {
        List<Edge> edges = Arrays.asList(
            new Edge(0,1,4), new Edge(0,2,8), new Edge(1,2,2),
            new Edge(2,1,1), new Edge(1,3,5), new Edge(2,3,3)
        );
        OptionalLong answer = directedMstCost(4, 0, edges);
        System.out.println(answer.isPresent() ? answer.getAsLong() : "infeasible"); // 9
    }
}

Input and tie-handling checklist

Complexity Analysis

In the basic implementation, each contraction round scans all edges to choose incoming minima and rebuild the graph. Every round contracts at least one directed cycle, reducing the number of current vertices:

More sophisticated implementations using meldable heaps, disjoint sets, and careful lazy weight adjustments improve the bound, including Tarjan-style $O(E\log V)$ variants. They also make reconstruction bookkeeping more intricate. For many moderate graphs, the transparent $O(VE)$ version is the safer engineering choice.

Directed Arborescence vs. Undirected MST

Real-World Applications

In score-maximization settings, the graph may be dense because every possible parent–child pair receives a model score. Domain constraints—such as forbidden parents, a single designated root, or required edges—must be encoded before running the algorithm.

Exercises

Limitations

Use a well-tested implementation when the edge set itself—not only its cost—is operationally important. Validate the returned parents by checking root indegree zero, every other indegree one, exactly $V-1$ edges, total cost, and reachability from the root.