Python 实现中国邮递员问题：从理论到动态可视化

图与网络 | 中国邮递员问题（CPP）Python 完整实现（含动态可视化）

中国邮递员问题（Chinese Postman Problem, CPP）是图论与网络优化中最经典的路径规划问题，由我国数学家管梅谷先生在 1960 年首次提出，并给出奇偶点图上作业法，该问题被国际学术界统一命名为 “中国邮递员问题”。

本文 用 Python 完整实现中国邮递员问题的求解，包含核心算法、代码注释、运行结果与动态可视化，可直接用于物流配送、路线巡检等工程场景。

unsetunset一、问题定义unsetunset

一名邮递员从邮局出发，必须走完辖区内所有街道至少一次，最终返回邮局，要求规划出总路程最短的行走路线。

用图论语言描述： 给定一个无向连通带权图，其中：

• ：顶点（街道交叉口 / 邮局）

• ：边（街道）

• ：边权（街道长度）

目标：找到一条闭合回路，遍历图中所有边至少一次，且总权值最小。

unsetunset二、核心算法原理（奇偶点图上作业法）unsetunset

中国邮递员问题的最优解，核心围绕欧拉回路展开：

1. 欧拉回路存在条件：图中所有顶点的度数均为偶数，此时直接遍历欧拉回路即为最优解（无重复边）。

2. 奇度顶点处理：若图中存在奇数个奇度顶点（必为偶数个），需将奇度顶点两两配对，并添加配对顶点间的最短路径（即重复行走对应街道），使所有顶点度数变为偶数。

3. 最优原则：配对的总路径权值最小，最终得到的欧拉图的欧拉回路即为最优路线。

标准求解步骤

1. 找出图中所有奇度顶点；

2. 对奇度顶点做最小权完美匹配；

3. 将匹配路径的边复制到原图，构造欧拉图；

4. 用 Hierholzer 算法求解欧拉图的欧拉回路，即最优路线。

unsetunset三、Python 实现（完整可运行）unsetunset

1. 依赖库安装

pip install networkx matplotlib

• heapq：堆优化 Dijkstra 最短路径

• networkx：图论算法（最小权完美匹配）

• matplotlib：静态绘图 + 动态动画可视化

2. 完整代码

import heapqimport randomimport networkx as nximport matplotlib.pyplot as pltfrom matplotlib.animation import FuncAnimationfrom collections import defaultdict# ===================== 配置参数 =====================CONFIG = {"mode": "manual",        # 手动/随机地图"nodes": 6,              # 随机图节点数"edge_density": 0.4,     # 边密度"weight_range": (1, 10), # 边权范围# 手动定义地图 (u, v, 权重)"manual_edges": [(0, 1, 1), (0, 2, 2), (1, 2, 3), (1, 3, 1), (2, 3, 2)],"speed": 800,            # 动画速度"seed": 42# 随机种子}# ===================== 1. Dijkstra最短路径 =====================defshortest_path(graph, start, end):    dist = {node: float('inf') for node in graph}    dist[start] = 0    prev = {node: Nonefor node in graph}    heap = [(0, start)]while heap:        d, u = heapq.heappop(heap)if d > dist[u]:continueif u == end:breakfor v, w in graph[u]:            nd = d + wif nd < dist[v]:                dist[v] = nd                prev[v] = u                heapq.heappush(heap, (nd, v))# 重构路径    path = []    cur = endwhile cur isnotNone:        path.append(cur)        cur = prev[cur]return path[::-1], dist[end]# ===================== 2. 提取奇度顶点 =====================defget_odd_nodes(graph):return [node for node, adj in graph.items() if len(adj) % 2 != 0]# ===================== 3. 最小权完美匹配 =====================defmin_matching(graph, odd_nodes):if len(odd_nodes) <= 1:return []# 构建奇度顶点完全图    complete_G = nx.Graph()for i in range(len(odd_nodes)):for j in range(i+1, len(odd_nodes)):            u, v = odd_nodes[i], odd_nodes[j]            _, d = shortest_path(graph, u, v)            complete_G.add_edge(u, v, weight=d)# 最小权完美匹配    matching = nx.algorithms.matching.min_weight_matching(complete_G)# 转换为原始图最短路径    match_paths = []for u, v in matching:        path, _ = shortest_path(graph, u, v)        match_paths.append(path)return match_paths# ===================== 4. 构造欧拉图 =====================defbuild_euler_graph(origin_graph, edges, match_paths):    euler_g = defaultdict(list)# 添加原始边for u, v, w in edges:        euler_g[u].append((v, w))        euler_g[v].append((u, w))# 复制匹配路径边for path in match_paths:for i in range(len(path)-1):            u, v = path[i], path[i+1]            w = next(wt for nb, wt in origin_graph[u] if nb == v)            euler_g[u].append((v, w))            euler_g[v].append((u, w))return euler_g# ===================== 5. Hierholzer算法求欧拉回路 =====================defeuler_tour(euler_graph, start=None):ifnot euler_graph:return []    start = start or next(iter(euler_graph.keys()))    stack, tour = [start], []    eg = {u: list(adj) for u, adj in euler_graph.items()}while stack:        cur = stack[-1]if eg.get(cur):            nxt, _ = eg[cur].pop()# 删除反向边for i, (nb, w) in enumerate(eg[nxt]):if nb == cur:del eg[nxt][i]break            stack.append(nxt)else:            tour.append(stack.pop())return tour[::-1]# ===================== 随机图生成 =====================defgenerate_random_graph(n, density, weight, seed=None):if seed:        random.seed(seed)    edges = set()    nodes = list(range(n))# 生成树保证连通for i in range(1, n):        u, v = nodes[i-1], nodes[i]        edges.add((min(u, v), max(u, v), random.randint(*weight)))# 补充随机边    max_e = n*(n-1)//2    target = int(density * max_e)while len(edges) < target:        u, v = random.sample(nodes, 2)        u, v = sorted((u, v))if (u, v) notin [(a,b) for a,b,_ in edges]:            edges.add((u, v, random.randint(*weight)))# 构建邻接表    graph = defaultdict(list)for u, v, w in edges:        graph[u].append((v, w))        graph[v].append((u, w))return list(edges), graph# ===================== 主程序 =====================if __name__ == "__main__":# 1. 构建图if CONFIG["mode"] == "random":        edges, graph = generate_random_graph(            CONFIG["nodes"], CONFIG["edge_density"],             CONFIG["weight_range"], CONFIG["seed"]        )else:        edges = CONFIG["manual_edges"]        graph = defaultdict(list)for u, v, w in edges:            graph[u].append((v, w))            graph[v].append((u, w))# 节点标签    node_label = {i: chr(ord('A')+i) for i in range(len(graph))}for i in range(26, len(graph)):        node_label[i] = str(i)# 2. 中国邮递员算法    odd_nodes = get_odd_nodes(graph)    print("奇度顶点：", [node_label[n] for n in odd_nodes])    match_paths = min_matching(graph, odd_nodes)    print("最小权匹配路径：")for p in match_paths:        print(" → ".join(node_label[n] for n in p))    euler_g = build_euler_graph(graph, edges, match_paths)    best_route = euler_tour(euler_g)# 计算总路程    weight = {(u,v):w for u,v,w in edges}    weight.update({(v,u):w for u,v,w in edges})    total_len = sum(weight[(a,b)] for a,b in zip(best_route, best_route[1:]))    print("\n最优路线：", " → ".join(node_label[n] for n in best_route))    print("最短总路程：", total_len)# 3. 可视化    plt.rcParams["font.sans-serif"] = ["SimHei"]    fig, ax = plt.subplots(figsize=(8, 8))    G = nx.Graph([(u,v) for u,v,_ in edges])    pos = nx.spring_layout(G, seed=CONFIG["seed"])# 绘制底图    nx.draw_networkx_nodes(G, pos, node_color="skyblue", node_size=1800)    nx.draw_networkx_labels(G, pos, node_label, font_size=16)    nx.draw_networkx_edges(G, pos, edge_color="gray", width=2, alpha=0.6)    nx.draw_networkx_edge_labels(G, pos, {(u,v):w for u,v,w in edges})# 标记重复边（红色虚线）    added_edges = {(min(u,v), max(u,v)) for p in match_paths for u,v in zip(p,p[1:])}    nx.draw_networkx_edges(G, pos, edgelist=list(added_edges),                            edge_color="red", style="--", width=2)# 动画元素    route_line, = ax.plot([], [], "r-", lw=4)    current_dot, = ax.plot([], [], "ro", markersize=14)    info_text = ax.text(0.02, 0.95, "", transform=ax.transAxes,                         bbox=dict(facecolor="white", alpha=0.7))    ax.set_title("中国邮递员问题 动态演示", fontsize=16)    ax.axis("off")    path_edges = list(zip(best_route, best_route[1:]))defupdate(frame):        x, y = [], []        current = best_route[frame+1]        total = 0for i in range(frame+1):            a, b = path_edges[i]            total += weight[(a,b)]            x += [pos[a][0], pos[b][0], None]            y += [pos[a][1], pos[b][1], None]        route_line.set_data(x, y)        current_dot.set_data([pos[current][0]], [pos[current][1]])        info_text.set_text(f"路线：{'→'.join(node_label[n] for n in best_route[:frame+2])}\n已走路程：{total}")return route_line, current_dot, info_text    ani = FuncAnimation(fig, update, frames=len(path_edges), interval=CONFIG["speed"])    plt.tight_layout()    plt.show()

unsetunset