最小树形图与 Chu–Liu–Edmonds 算法

形式陈述 ​

问题与局部选择 ​

给定带实权的有限有向图公理库有向图Directed graph · Digraph以顶点有序对为弧、能够保留连接方向的有限简单图结构。 $D=(V,A)$ 和根 $r$，入树形图是以 $r$ 为根的有向生成结构：每个 $v\ne r$ 恰有一条选中入弧，$r$ 没有选中入弧，并且从 $r$ 可沿选中弧到达所有顶点。目标是使选中弧总权最小。若某个顶点从 $r$ 不可达，则实例无解。

Chu–Liu–Edmonds 先做一次局部贪心选择公理库贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。：对每个 $v\ne r$ 选一条最轻入弧 $e_v$，并排除指向根的弧。若这些弧没有形成有向圈，它们已经让每个非根顶点恰有一个父弧，并且根可达所有顶点；每个顶点都达到独立的最轻入弧下界，所以所得树形图最优。

缩环、重赋权与展开 ​

若选中弧形成有向圈 $C$，任何根树形图都必须用一条外部弧 $(u,v)$ 进入 $C$，并舍弃圈中原来指向 $v$ 的 $e_v$。把 $C$ 收缩为超点，对每条进入 $v\in C$ 的外部弧定义

$$c^{\prime }(u,C)=c(u,v)-c(e_v).$$

圈内基准成本 $\sum _{x\in C}c(e_x)$ 已经统一支付，$c(u,v)-c(e_v)$ 正是选择外部弧、替换 $e_v$ 所增加的成本。离开 $C$ 的弧和圈外弧保持原权；收缩产生的平行弧必须保留各自原弧身份。递归求缩图的最优树形图后，若递归解选择了原终点为 $v$ 的进入超点弧，就保留该外部弧、删除 $e_v$，并保留圈中其余选中弧。

正确性不变量 ​

每个可行原解都恰好选择一条进入 $C$ 的弧，并在该弧的终点处打破圈；减去统一基准成本后，它与一个缩图可行解一一对应。反过来，每个进入超点的缩图解都能按原弧映射展开，恢复所有非根顶点唯一入弧和根可达性。因此缩图最优选择进入哪个顶点，等价于原图最优选择在哪里破圈。

多层收缩时，这个对应关系逐层嵌套。实现必须为每层保存圈成员、各顶点选中的 $e_v$、重赋权弧对应的原弧及其原终点，并按收缩的逆序展开；只保存新端点与新费用无法恢复原始弧集合。

直觉

“每个顶点各取最便宜入弧”给出了一个可加的局部下界，却可能把若干顶点锁成没有根入口的圈。收缩不把这个失败藏起来，而是先把圈内已经支付的最低成本打包，再让所有外部入口在同一超点上比较“为了从哪个顶点破圈，需要额外多付多少”。递归只选择这笔替换代价，展开时再把局部下界与替换决定拼回完整树形图。

它不是 Prim 或 Kruskal 加上箭头。无向生成树的割性质选择连接两个分量的边；树形图还要求每个非根顶点恰有一条入弧，并从指定根沿方向可达。方向与根改变了可行集，缩环才是这里的核心修复动作。

例子与边界

三个非根顶点的最轻入弧可能形成 $a\to b\to c\to a$。直接任选一弧删除，可能迫使使用一条极贵的外部入口；重赋权则分别计算外弧进入 $a,b,c$ 时替换对应最轻入弧的增量，让递归选择真正便宜的破圈位置。

根、入树形图还是出树形图、最小还是最大版本会整体改变弧方向或目标。负权不妨碍“相对基准成本”的推导；平行弧也可处理，但端点相同不代表身份相同。若收缩超点不含根，却没有任何可选外部入弧，则原图中该圈所在部分从根不可达，实例无解。未指定根的 optimum branching 又是不同问题。

推论与应用

经典朴素实现逐轮选入弧、找圈、收缩和展开，时间为 $O(|V||A|)$；更快版本使用可合并堆等结构维护重赋权候选。无论追求哪一复杂度，都必须排除根的入弧，保存原弧身份，并在返回答案时给出一组真实原弧而非只有收缩图上的超点边。

最小树形图用于有向网络设计、依赖选择和根可达结构优化。它与最小生成树公理库最小生成树Minimum spanning tree · MST连通加权图中总边权最小的生成树及其算法问题。共享“生成结构”一词，但可行性、交换论证和算法状态均不同；与一般最短路树相比，它优化所有选中弧的总权，而不是逐顶点的根到点距离。

参考资料

• Yoeng-Jin Chu, Tseng-Hong Liu, On the Shortest Arborescence of a Directed Graph, 1965.
• Jack Edmonds, Optimum Branchings, J. Research NBS, 1967.
• Robert Tarjan, Finding Optimum Branchings, Networks, 1977.