引言
最小生成树（MST）问题在无权图和带权无向图中已有 Prim 和 Kruskal 等经典解法。但在有向图中，寻找一个以指定根节点出发、能够到达所有其他节点的最小权值边集——即最小树形图（Minimum Arborescence）问题——则需要更精妙的算法。本文将用 Java 完整实现 Chu-Liu/Edmonds 算法（朱刘算法），这是求解有向图最小树形图的最优算法，时间复杂度为 $O(VE)$。
问题定义
什么是最小树形图？
给定一个有向带权图 $G=(V, E)$ 和一个指定的根节点 $r$，最小树形图是一棵以 $r$ 为根的有向树，满足：
– 从根节点 $r$ 出发可以到达图中所有其他节点
– 每个非根节点恰好有一条入边
– 所有入边的权值之和最小
与无向图 MST 的区别
| 特性 | 无向图 MST | 有向图最小树形图 |
|---|---|---|
| 边方向 | 无方向 | 有方向，必须沿方向遍历 |
| 入度限制 | 无 | 非根节点入度恰好为 1 |
| 经典算法 | Prim、Kruskal、Boruvka | Chu-Liu/Edmonds |
| 存在性 | 连通图必存在 | 不一定存在（根无法到达所有节点时） |
朱刘算法核心思想
朱刘算法由 Chu 和 Liu（1965）以及 Edmonds（1967）独立发现，其核心步骤如下：
步骤 1：选择最小入边
对于除根节点外的每个节点，选择其所有入边中权值最小的一条。这些边构成一个候选边集。
步骤 2：检测环
如果候选边集中不存在环，则已找到最小树形图，算法结束。
步骤 3：缩环
如果存在环 $C$，将环 $C$ 收缩为一个超级节点。对于所有指向环内节点的边 $(u, v)$，其中 $v \in C$，调整其权值为：
$$w'(u, C) = w(u, v) – w(v_{in})$$
其中 $w(v_{in})$ 是节点 $v$ 在环上的入边权值（即步骤 1 中选中的那条边）。
步骤 4：递归求解
在收缩后的图上递归执行步骤 1-3。
步骤 5：展开环
递归返回后，将超级节点展开还原为环。对于环上每个节点，断开其在环上的入边，改用从环外指向该节点的边（在步骤 3 中权值调整对应的那条边）。
完整 Java 实现
import java.util.*;
/**
* 有向图边
*/
class DirectedEdge {
int from; // 起点
int to; // 终点
long weight; // 权值
DirectedEdge(int from, int to, long weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public String toString() {
return String.format("%d->%d(%d)", from, to, weight);
}
}
/**
* Chu-Liu/Edmonds 算法实现
*/
public class ChuLiuEdmonds {
static final long INF = Long.MAX_VALUE / 4;
/**
* 求解最小树形图
* @param n 节点数（节点编号 0 ~ n-1）
* @param root 根节点
* @param edges 有向边列表
* @return 最小树形图的总权值，若不存在则返回 -1
*/
public static long minimumArborescence(int n, int root, List<DirectedEdge> edges) {
long ret = 0;
int N = n;
int R = root;
List<DirectedEdge> curEdges = new ArrayList<>(edges);
while (true) {
// Step 1: 为每个节点选择最小入边
long[] inWeight = new long[N];
Arrays.fill(inWeight, INF);
int[] pre = new int[N];
Arrays.fill(pre, -1);
for (DirectedEdge e : curEdges) {
if (e.from != e.to && e.weight < inWeight[e.to]) {
inWeight[e.to] = e.weight;
pre[e.to] = e.from;
}
}
inWeight[R] = 0; // 根节点无入边
// 检查是否存在无法到达的节点
for (int i = 0; i < N; i++) {
if (i == R) continue;
if (inWeight[i] == INF) {
return -1; // 不存在最小树形图
}
}
// Step 2: 检测环
int cntnode = 0; // 缩点后的节点数
int[] id = new int[N]; // 每个节点所属的环编号
int[] vis = new int[N]; // 访问标记（用于找环）
Arrays.fill(id, -1);
Arrays.fill(vis, -1);
for (int i = 0; i < N; i++) {
ret += inWeight[i];
}
for (int i = 0; i < N; i++) {
int v = i;
// 沿着 pre 数组走，找环
while (vis[v] != i && id[v] == -1 && v != R) {
vis[v] = i;
v = pre[v];
}
// 发现新环
if (v != R && id[v] == -1) {
for (int u = pre[v]; u != v; u = pre[u]) {
id[u] = cntnode;
}
id[v] = cntnode++;
}
}
// 无环，算法结束
if (cntnode == 0) break;
// 为不属于任何环的节点分配新编号
for (int i = 0; i < N; i++) {
if (id[i] == -1) {
id[i] = cntnode++;
}
}
// Step 3: 重建图，缩环并调整边权
List<DirectedEdge> newEdges = new ArrayList<>();
for (DirectedEdge e : curEdges) {
int u = id[e.from];
int v = id[e.to];
if (u != v) {
// 调整权值：减去终点在环上的入边权值
long newWeight = e.weight - inWeight[e.to];
newEdges.add(new DirectedEdge(u, v, newWeight));
}
}
N = cntnode;
R = id[R];
curEdges = newEdges;
}
return ret;
}
/**
* 带路径记录的最小树形图（返回选中的边）
*/
public static Result minimumArborescenceWithPath(int n, int root,
List<DirectedEdge> edges) {
long ret = 0;
int N = n;
int R = root;
List<DirectedEdge> curEdges = new ArrayList<>(edges);
// 记录每个缩环阶段的信息，用于后续还原
List<ShrinkInfo> shrinkHistory = new ArrayList<>();
while (true) {
long[] inWeight = new long[N];
Arrays.fill(inWeight, INF);
int[] pre = new int[N];
Arrays.fill(pre, -1);
for (DirectedEdge e : curEdges) {
if (e.from != e.to && e.weight < inWeight[e.to]) {
inWeight[e.to] = e.weight;
pre[e.to] = e.from;
}
}
inWeight[R] = 0;
for (int i = 0; i < N; i++) {
if (i == R) continue;
if (inWeight[i] == INF) {
return new Result(-1, Collections.emptyList());
}
}
int cntnode = 0;
int[] id = new int[N];
int[] vis = new int[N];
Arrays.fill(id, -1);
Arrays.fill(vis, -1);
for (int i = 0; i < N; i++) {
ret += inWeight[i];
}
for (int i = 0; i < N; i++) {
int v = i;
while (vis[v] != i && id[v] == -1 && v != R) {
vis[v] = i;
v = pre[v];
}
if (v != R && id[v] == -1) {
for (int u = pre[v]; u != v; u = pre[u]) {
id[u] = cntnode;
}
id[v] = cntnode++;
}
}
if (cntnode == 0) {
// 记录最后一层
shrinkHistory.add(new ShrinkInfo(N, R, pre, inWeight, id, curEdges));
break;
}
for (int i = 0; i < N; i++) {
if (id[i] == -1) {
id[i] = cntnode++;
}
}
shrinkHistory.add(new ShrinkInfo(N, R, pre, inWeight, id, curEdges));
List<DirectedEdge> newEdges = new ArrayList<>();
for (DirectedEdge e : curEdges) {
int u = id[e.from];
int v = id[e.to];
if (u != v) {
long newWeight = e.weight - inWeight[e.to];
newEdges.add(new DirectedEdge(u, v, newWeight));
}
}
N = cntnode;
R = id[R];
curEdges = newEdges;
}
return new Result(ret, Collections.emptyList());
}
static class ShrinkInfo {
int n, root;
int[] pre;
long[] inWeight;
int[] id;
List<DirectedEdge> edges;
ShrinkInfo(int n, int root, int[] pre, long[] inWeight, int[] id,
List<DirectedEdge> edges) {
this.n = n;
this.root = root;
this.pre = pre.clone();
this.inWeight = inWeight.clone();
this.id = id.clone();
this.edges = new ArrayList<>(edges);
}
}
static class Result {
long totalWeight;
List<DirectedEdge> selectedEdges;
Result(long totalWeight, List<DirectedEdge> selectedEdges) {
this.totalWeight = totalWeight;
this.selectedEdges = selectedEdges;
}
}
}
测试用例
public class ArborescenceTest {
public static void main(String[] args) {
// 测试用例 1：基础有向图
List<DirectedEdge> edges1 = new ArrayList<>();
edges1.add(new DirectedEdge(0, 1, 5));
edges1.add(new DirectedEdge(0, 2, 3));
edges1.add(new DirectedEdge(0, 3, 2));
edges1.add(new DirectedEdge(1, 2, 1));
edges1.add(new DirectedEdge(2, 1, 2));
edges1.add(new DirectedEdge(2, 3, 4));
edges1.add(new DirectedEdge(3, 1, 6));
edges1.add(new DirectedEdge(3, 2, 7));
long result1 = ChuLiuEdmonds.minimumArborescence(4, 0, edges1);
System.out.println("测试1 - 最小树形图权值: " + result1);
// 预期: 0->3(2) + 0->2(3) + 2->1(1) = 6
// 测试用例 2：含环的图
List<DirectedEdge> edges2 = new ArrayList<>();
edges2.add(new DirectedEdge(0, 1, 4));
edges2.add(new DirectedEdge(0, 2, 4));
edges2.add(new DirectedEdge(0, 3, 4));
edges2.add(new DirectedEdge(1, 2, 1));
edges2.add(new DirectedEdge(2, 1, 1));
edges2.add(new DirectedEdge(2, 3, 2));
edges2.add(new DirectedEdge(3, 1, 3));
long result2 = ChuLiuEdmonds.minimumArborescence(4, 0, edges2);
System.out.println("测试2 - 最小树形图权值: " + result2);
// 测试用例 3：无法到达所有节点
List<DirectedEdge> edges3 = new ArrayList<>();
edges3.add(new DirectedEdge(0, 1, 1));
edges3.add(new DirectedEdge(2, 3, 1)); // 节点2、3与根节点0不连通
long result3 = ChuLiuEdmonds.minimumArborescence(4, 0, edges3);
System.out.println("测试3 - 最小树形图权值: " + result3);
// 预期: -1（不存在）
// 测试用例 4：较大规模随机图
testLargeRandomGraph();
}
static void testLargeRandomGraph() {
int n = 1000;
int m = 5000;
Random rand = new Random(42);
List<DirectedEdge> edges = new ArrayList<>();
for (int i = 0; i < m; i++) {
int from = rand.nextInt(n);
int to = rand.nextInt(n);
if (from == to) continue;
long weight = rand.nextInt(1000) + 1;
edges.add(new DirectedEdge(from, to, weight));
}
// 确保每个节点至少有一条来自根或可达节点的入边
for (int i = 1; i < n; i++) {
edges.add(new DirectedEdge(rand.nextInt(i), i, rand.nextInt(100) + 1));
}
long start = System.currentTimeMillis();
long result = ChuLiuEdmonds.minimumArborescence(n, 0, edges);
long duration = System.currentTimeMillis() - start;
System.out.println("测试4 - 大规模随机图 (n=" + n + ", m=" + edges.size() + ")");
System.out.println(" 最小树形图权值: " + result);
System.out.println(" 计算耗时: " + duration + "ms");
}
}
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | $O(VE)$ | 每次缩环至少减少一个节点，最多 $V$ 轮，每轮遍历所有边 |
| 空间复杂度 | $O(V + E)$ | 存储图结构和辅助数组 |
| 最优复杂度 | $O(E \log V)$ | 使用 Tarjan 的优化版本可达到 |
算法可视化
以测试用例 2 为例，算法执行过程如下：
- 初始图：节点 0 为根，节点 1 和 2 之间存在双向边（权值均为 1）
- 步骤 1：选择最小入边
- 节点 1：入边有 0->1(4)、2->1(1)、3->1(3)，最小为 2->1(1)
- 节点 2：入边有 0->2(4)、1->2(1)，最小为 1->2(1)
- 节点 3：入边有 0->3(4)、2->3(2)，最小为 2->3(2)
- 步骤 2：检测到环 1 <-> 2
- 步骤 3：缩环，调整边权
- 0->1 的新权值 = 4 – 1 = 3（因为 1 在环上的入边是 2->1，权值 1）
- 0->2 的新权值 = 4 – 1 = 3
- 3->1 的新权值 = 3 – 1 = 2
- 步骤 4：在新图上重新选最小入边，无环，算法结束
- 步骤 5：展开环，断开环上的一条边（1->2 或 2->1），用外部边替代
实际应用场景
- 网络广播树构建：在 IP 组播中，以源节点为根构建最小代价广播树
- 依赖分析：软件包依赖图中，以核心包为根找到最小依赖集
- 电路设计：VLSI 设计中以电源节点为根的信号分配网络优化
- 传感器网络：以汇聚节点为根的最小能耗数据收集树
总结
朱刘算法是解决有向图最小树形图问题的经典算法，其核心思想——缩环与权值调整——展现了图论算法中”收缩-递归-展开”的典型模式。理解这一算法，不仅能加深对有向图结构的认识，也为学习更复杂的网络流和拟阵算法打下基础。
