当前位置：首页 > news >正文

有向图最小生成树：朱刘算法原理与实战解析

news 2026/5/11 16:56:16

1. 什么是有向图最小生成树？

想象一下你正在规划一座城市的单向交通网络。每条道路都有方向（比如单行道），且修建成本不同。你需要选择一组道路，使得从市政府（根节点）能到达所有其他地点，同时总修建成本最低——这就是有向图最小生成树（也叫最小树形图）要解决的问题。

与常见的无向图最小生成树（如Kruskal算法解决的问题）不同，有向图的边具有方向性。举个生活例子：无向图就像双向通行的马路，修路时只需考虑道路长度；而有向图类似单行道系统，不仅要看道路成本，还要确保方向组合能让车辆从中心点到达所有区域。

2. 为什么需要朱刘算法？

2.1 传统算法的局限性

Prim和Kruskal算法在无向图中表现优异，但直接套用到有向图会翻车。比如下图：

A → B (成本1) B → A (成本5) C → A (成本2)

若以A为根，Kruskal可能选择B→A和C→A（总成本7），但最优解其实是A→B和C→A（总成本3）。

2.2 朱刘算法的核心思想

朱刘算法（Chu-Liu/Edmonds算法）的巧妙之处在于两个关键操作：

贪心选最小入边：每个非根节点先选最小成本的入边
缩点破环：如果形成有向环，就把整个环"捏"成一个超级节点

这就好比建筑队先粗选最便宜的进口材料（可能形成供货闭环），发现闭环后就把整个供应商联盟当作一个批发市场重新议价。

3. 算法步骤详解

3.1 初始化阶段

def zhuliu(root, n, edges): res = 0 # 总成本 while True: # 1. 初始化最小入边数组 in_cost = [float('inf')] * n pre = [-1] * n # 前驱节点

3.2 找最小入边

# 2. 寻找每个点的最小入边 for u, v, w in edges: if u != v and w < in_cost[v]: in_cost[v] = w pre[v] = u

3.3 检查不可解情况

# 3. 检查是否存在不可达点 for v in range(n): if v != root and in_cost[v] == float('inf'): return -1 # 无解

3.4 检测与收缩环

# 4. 找环并收缩 visited = [-1] * n new_id = [-1] * n tn = 0 # 新节点计数 for v in range(n): res += in_cost[v] u = v # 找环 while visited[u] != v and new_id[u] == -1 and u != root: visited[u] = v u = pre[u] # 发现新环 if u != root and new_id[u] == -1: # 给环内节点重新编号 while new_id[u] == -1: new_id[u] = tn u = pre[u] tn += 1

3.5 无环时退出

if tn == 0: # 无环 break

3.6 处理剩余节点

# 给非环节点编号 for v in range(n): if new_id[v] == -1: new_id[v] = tn tn += 1

4. 实战案例解析

4.1 POJ3164 军事通信网络

题目给出N个军事基地的坐标和M条单向通信线路，要求建立从总部出发覆盖所有基地的最小成本网络。

关键点处理：

# 计算两点间欧氏距离 def get_dist(a, b): return math.sqrt((a.x-b.x)**2 + (a.y-b.y)**2) # 构建边集 edges = [] for _ in range(m): u, v = map(int, input().split()) if u != v: # 排除自环 w = get_dist(points[u-1], points[v-1]) edges.append((u-1, v-1, w))

4.2 HDU2121 冰淇淋王国

需要为N个城市设计单向配送路线，但不指定总部位置。

虚根技巧：

# 添加虚根，连接到所有城市 sum_cost = sum(w for _,_,w in edges) + 1 for v in range(n): edges.append((n, v, sum_cost)) # 运行朱刘算法后 if result >= 2 * sum_cost: print("impossible") else: print(result - sum_cost)