问题背景
中国邮路问题（Chinese Postman Problem, CPP）是图论中的经典优化问题：邮递员需要遍历某片区内的所有街道至少一次并返回邮局，如何选择路线使总行驶距离最短？
该问题由我国数学家管梅谷教授于1962年首次系统研究并给出多项式时间算法，因此被国际学术界命名为”中国邮路问题”。它与旅行商问题（TSP）不同：TSP要求每个顶点只访问一次，而CPP要求每条边至少访问一次。
核心算法思路
问题分类
根据图的类型，中国邮路问题分为三种情况：
- 无向图CPP：所有边无方向，算法最简洁
- 有向图CPP：所有边有方向，需用网络流求解
- 混合图CPP：既有有向边又有无向边，是NP-hard问题
本文聚焦无向图CPP的求解。
核心定理
欧拉回路存在条件：无向图存在欧拉回路（经过每条边恰好一次并回到起点的闭合路径）当且仅当图是连通的且所有顶点的度数均为偶数。
因此，若图中所有顶点度数为偶数，中国邮路问题的最优解就是欧拉回路本身。若存在奇度顶点（根据握手定理，奇度顶点个数必为偶数），则需要对某些边进行重复遍历，使得所有顶点度数变为偶数。
算法步骤
- 找出所有奇度顶点：设共有 $2k$ 个
- 计算奇度顶点之间的最短路径：使用Floyd-Warshall或Dijkstra算法
- 最小权完美匹配：在 $2k$ 个奇度顶点之间寻找 $k$ 对配对，使得配对的顶点间最短路径之和最小
- 复制匹配边：将匹配中的最短路径上的每条边复制一份（相当于重复走一次）
- 求欧拉回路：在修改后的图中使用Hierholzer算法求欧拉回路
Java 完整实现
import java.util.*;
/**
* 中国邮路问题求解器（无向图版本）
* 使用最小权完美匹配 + Hierholzer算法求欧拉回路
*/
public class ChinesePostmanSolver {
// 无穷大表示
private static final int INF = Integer.MAX_VALUE / 2;
private int n; // 顶点数
private int[][] dist; // 最短距离矩阵（Floyd结果）
private int[][] originalDist; // 原始边权
private List<int[]>[] adj; // 邻接表（用于欧拉回路），存储 [邻接点, 边权, 边id]
private int edgeCount;
private int startVertex; // 起点
/**
* 构造函数
* @param n 顶点数（顶点编号 0 到 n-1）
* @param edges 边列表，每个元素为 int[]{u, v, w}
* @param start 起点
*/
@SuppressWarnings("unchecked")
public ChinesePostmanSolver(int n, List<int[]> edges, int start) {
this.n = n;
this.startVertex = start;
this.originalDist = new int[n][n];
this.dist = new int[n][n];
this.adj = new ArrayList[n];
this.edgeCount = 0;
for (int i = 0; i < n; i++) {
Arrays.fill(originalDist[i], INF);
Arrays.fill(dist[i], INF);
originalDist[i][i] = 0;
dist[i][i] = 0;
adj[i] = new ArrayList<>();
}
for (int[] e : edges) {
int u = e[0], v = e[1], w = e[2];
originalDist[u][v] = Math.min(originalDist[u][v], w);
originalDist[v][u] = Math.min(originalDist[v][u], w);
dist[u][v] = originalDist[u][v];
dist[v][u] = originalDist[v][u];
// 添加双向边到邻接表
adj[u].add(new int[]{v, w, edgeCount});
adj[v].add(new int[]{u, w, edgeCount});
edgeCount++;
}
}
/**
* Floyd-Warshall算法求全源最短路径
*/
public void floydWarshall() {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
if (dist[i][k] == INF) continue;
for (int j = 0; j < n; j++) {
if (dist[k][j] == INF) continue;
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
/**
* 获取奇度顶点列表
*/
public List<Integer> getOddDegreeVertices() {
int[] degree = new int[n];
for (int u = 0; u < n; u++) {
for (int[] e : adj[u]) {
if (e[2] >= 0) { // 有效边
degree[u]++;
}
}
}
// 上面的degree计算会每条边算两次，但这不影响奇偶性
List<Integer> odd = new ArrayList<>();
for (int i = 0; i < n; i++) {
// 重新准确计算度数
Set<Integer> neighbors = new HashSet<>();
int deg = 0;
for (int[] e : adj[i]) {
deg++;
}
if (deg % 2 == 1) {
odd.add(i);
}
}
return odd;
}
/**
* 使用状压DP求最小权完美匹配
* @param oddVertices 奇度顶点列表
* @return 最小匹配权值和配对方案
*/
public Pair<Integer, List<int[]>> minWeightPerfectMatching(List<Integer> oddVertices) {
int m = oddVertices.size();
if (m == 0) return new Pair<>(0, new ArrayList<>());
int[] odd = new int[m];
for (int i = 0; i < m; i++) odd[i] = oddVertices.get(i);
// dp[mask] 表示 mask 中的顶点已完成匹配的最小权值
int[] dp = new int[1 << m];
Arrays.fill(dp, INF);
dp[0] = 0;
// 记录前驱用于回溯
int[] pre = new int[1 << m];
Arrays.fill(pre, -1);
for (int mask = 0; mask < (1 << m); mask++) {
if (dp[mask] == INF) continue;
// 找到第一个未匹配的顶点
int first = -1;
for (int i = 0; i < m; i++) {
if ((mask & (1 << i)) == 0) {
first = i;
break;
}
}
if (first == -1) continue;
for (int j = first + 1; j < m; j++) {
if ((mask & (1 << j)) != 0) continue;
int newMask = mask | (1 << first) | (1 << j);
int w = dist[odd[first]][odd[j]];
if (w >= INF) continue; // 不连通
if (dp[newMask] > dp[mask] + w) {
dp[newMask] = dp[mask] + w;
pre[newMask] = mask;
}
}
}
// 回溯配对方案
List<int[]> pairs = new ArrayList<>();
int mask = (1 << m) - 1;
while (pre[mask] != -1) {
int prev = pre[mask];
int diff = mask ^ prev;
// 找出diff中两个位
int a = -1, b = -1;
for (int i = 0; i < m; i++) {
if ((diff & (1 << i)) != 0) {
if (a == -1) a = i;
else b = i;
}
}
pairs.add(new int[]{odd[a], odd[b]});
mask = prev;
}
return new Pair<>(dp[(1 << m) - 1], pairs);
}
/**
* Hierholzer算法求欧拉回路
* @return 欧拉回路的顶点序列
*/
public List<Integer> eulerianCircuit() {
// 复制邻接表用于删除边
List<int[]>[] tempAdj = new ArrayList[n];
for (int i = 0; i < n; i++) {
tempAdj[i] = new ArrayList<>();
for (int[] e : adj[i]) {
tempAdj[i].add(e.clone());
}
}
List<Integer> circuit = new ArrayList<>();
Deque<Integer> stack = new ArrayDeque<>();
stack.push(startVertex);
while (!stack.isEmpty()) {
int u = stack.peek();
boolean hasEdge = false;
for (Iterator<int[]> it = tempAdj[u].iterator(); it.hasNext(); ) {
int[] e = it.next();
int v = e[0];
// 在v的邻接表中删除这条边
for (Iterator<int[]> it2 = tempAdj[v].iterator(); it2.hasNext(); ) {
int[] e2 = it2.next();
if (e2[0] == u && e2[2] == e[2]) {
it2.remove();
break;
}
}
it.remove();
stack.push(v);
hasEdge = true;
break;
}
if (!hasEdge) {
circuit.add(stack.pop());
}
}
Collections.reverse(circuit);
return circuit;
}
/**
* 求解中国邮路问题
* @return 最优路线总长度和顶点序列
*/
public Result solve() {
// 1. 求全源最短路径
floydWarshall();
// 2. 检查连通性
for (int i = 0; i < n; i++) {
if (dist[startVertex][i] == INF) {
return new Result(-1, null); // 图不连通
}
}
// 3. 计算原始图所有边权之和
int originalSum = 0;
Set<String> counted = new HashSet<>();
for (int u = 0; u < n; u++) {
for (int[] e : adj[u]) {
int v = e[0];
String key = Math.min(u, v) + "-" + Math.max(u, v);
if (!counted.contains(key)) {
originalSum += e[1];
counted.add(key);
}
}
}
// 4. 找出奇度顶点
List<Integer> oddVertices = getOddDegreeVertices();
// 5. 最小权完美匹配
Pair<Integer, List<int[]>> matching = minWeightPerfectMatching(oddVertices);
int extraCost = matching.first;
// 6. 构建辅助图：为匹配的每对顶点添加"虚拟"重复边
// 这里我们记录需要重复的边，而不真的修改图结构
List<int[]> duplicatedEdges = new ArrayList<>();
for (int[] pair : matching.second) {
int u = pair[0], v = pair[1];
// 找到u到v的最短路径上的边
findPathEdges(u, v, duplicatedEdges);
}
// 7. 将重复的边加入邻接表（真正修改图使其成为欧拉图）
for (int[] edge : duplicatedEdges) {
int u = edge[0], v = edge[1], w = edge[2];
adj[u].add(new int[]{v, w, edgeCount});
adj[v].add(new int[]{u, w, edgeCount});
edgeCount++;
}
// 8. 求欧拉回路
List<Integer> circuit = eulerianCircuit();
int totalCost = originalSum + extraCost;
return new Result(totalCost, circuit);
}
/**
* 回溯找出u到v最短路径上的边
*/
private void findPathEdges(int u, int v, List<int[]> edges) {
// 使用Floyd的中间点信息或简单回溯
// 这里用贪心：每次找使 dist[u][v] = w(u,k) + dist[k][v] 成立的k
while (u != v) {
for (int[] e : adj[u]) {
int k = e[0];
int w = e[1];
// 检查是否 u->k 是最短路径的一部分
if (w + dist[k][v] == dist[u][v]) {
edges.add(new int[]{u, k, w});
u = k;
break;
}
}
}
}
// ========== 辅助类 ==========
static class Pair<F, S> {
F first;
S second;
Pair(F f, S s) { first = f; second = s; }
}
static class Result {
int totalCost;
List<Integer> circuit;
Result(int c, List<Integer> p) { totalCost = c; circuit = p; }
}
// ==================== 主程序 ====================
public static void main(String[] args) {
System.out.println("=== 中国邮路问题求解演示 ===\n");
// 示例1：所有顶点度数为偶数，本身就是欧拉图
System.out.println("示例1：欧拉图（所有顶点度数为偶数）");
List<int[]> edges1 = Arrays.asList(
new int[]{0, 1, 2},
new int[]{1, 2, 3},
new int[]{2, 3, 2},
new int[]{3, 0, 3},
new int[]{0, 2, 1},
new int[]{1, 3, 1}
);
ChinesePostmanSolver cpp1 = new ChinesePostmanSolver(4, edges1, 0);
Result r1 = cpp1.solve();
System.out.println("最优路线总长度: " + r1.totalCost);
System.out.println("欧拉回路: " + r1.circuit);
System.out.println();
// 示例2：存在奇度顶点
System.out.println("示例2：存在奇度顶点（需要重复走某些边）");
List<int[]> edges2 = Arrays.asList(
new int[]{0, 1, 4},
new int[]{1, 2, 2},
new int[]{2, 3, 3},
new int[]{3, 0, 5},
new int[]{0, 2, 1}
);
ChinesePostmanSolver cpp2 = new ChinesePostmanSolver(4, edges2, 0);
Result r2 = cpp2.solve();
System.out.println("最优路线总长度: " + r2.totalCost);
System.out.println("最优路线顶点序列: " + r2.circuit);
System.out.println();
// 示例3：更复杂的图
System.out.println("示例3：6个顶点的街道图");
List<int[]> edges3 = Arrays.asList(
new int[]{0, 1, 3},
new int[]{1, 2, 4},
new int[]{2, 3, 2},
new int[]{3, 4, 5},
new int[]{4, 5, 3},
new int[]{5, 0, 4},
new int[]{0, 3, 6},
new int[]{1, 4, 2}
);
ChinesePostmanSolver cpp3 = new ChinesePostmanSolver(6, edges3, 0);
Result r3 = cpp3.solve();
System.out.println("最优路线总长度: " + r3.totalCost);
System.out.println("最优路线顶点序列: " + r3.circuit);
}
}
算法复杂度分析
Floyd-Warshall 全源最短路径：
– 时间复杂度：$O(n^3)$
– 空间复杂度：$O(n^2)$
最小权完美匹配（状压DP）：
– 设奇度顶点数为 $2k$（$k \leq n/2$）
– 时间复杂度：$O(2^{2k} \cdot k^2)$，当 $k$ 较小时（实际街道网络中奇度顶点通常很少）非常高效
– 对于一般情况，可以使用 Edmonds 的 Blossom 算法，复杂度 $O(n^3)$
Hierholzer 欧拉回路：
– 时间复杂度：$O(|E|)$
– 空间复杂度：$O(|E|)$
总体复杂度：$O(n^3 + 2^{2k} \cdot k^2 + |E|)$，对于实际规模的街道网络完全可行。
关键结论与扩展
- 问题转化思想：中国邮路问题的核心是将”重复走边”转化为”奇度顶点配对”，这是图论中化归思想的典范。
- 欧拉回路存在条件：所有顶点度数为偶数是充要条件，这一简洁的判定条件使得问题可解。
- 有向图CPP：需要找到使每个顶点入度等于出度的最小增流方案，可用最小费用最大流求解。
- 实际应用：除邮路规划外，还应用于道路清扫、垃圾收集、电路板钻孔路径优化、DNA测序等场景。
总结
中国邮路问题是图论与实际应用完美结合的典范。从管梅谷教授的开创性工作到今天，该问题的求解框架（最短路径 + 最小权匹配 + 欧拉回路）已成为组合优化教学的经典案例。掌握这一算法，不仅能解决具体的路线规划问题，更能体会到”将复杂问题分解为熟悉子问题”这一算法设计的核心思想。
