Python案例如何用Networkx做中国邮递员

wen python案例 2026-07-16 220

本文目录导读：

中国邮递员问题简介
完整实现代码
代码说明

我来为你详细讲解如何使用NetworkX解决中国邮递员问题（Chinese Postman Problem）。

中国邮递员问题简介

中国邮递员问题：邮递员从邮局出发，走遍所有街道（边）至少一次，最后回到邮局，求最短路径。

完整实现代码

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
from itertools import permutations
import random
class ChinesePostmanSolver:
    def __init__(self):
        self.graph = None
        self.odd_vertices = []
        self.eulerian_circuit = []
    def create_example_graph(self):
        """创建示例图"""
        # 方式1：手动创建图
        G = nx.Graph()
        edges = [
            (0, 1, 2), (0, 2, 3), (1, 2, 1), (1, 3, 4),
            (2, 3, 2), (2, 4, 3), (3, 4, 5), (3, 5, 2),
            (4, 5, 1), (4, 6, 4), (5, 6, 3), (0, 4, 6)
        ]
        G.add_weighted_edges_from(edges)
        return G
    def create_random_graph(self, n_nodes=8, n_edges=15, seed=42):
        """创建随机图"""
        random.seed(seed)
        np.random.seed(seed)
        G = nx.Graph()
        # 添加节点
        G.add_nodes_from(range(n_nodes))
        # 添加随机边
        edges_added = 0
        while edges_added < n_edges:
            u = random.randint(0, n_nodes-1)
            v = random.randint(0, n_nodes-1)
            if u != v and not G.has_edge(u, v):
                weight = random.randint(1, 10)
                G.add_edge(u, v, weight=weight)
                edges_added += 1
        # 确保图连通
        if not nx.is_connected(G):
            components = list(nx.connected_components(G))
            for i in range(len(components)-1):
                u = list(components[i])[0]
                v = list(components[i+1])[0]
                G.add_edge(u, v, weight=5)
        return G
    def find_odd_vertices(self):
        """找出奇度数顶点"""
        self.odd_vertices = []
        for node in self.graph.nodes():
            if self.graph.degree(node) % 2 == 1:
                self.odd_vertices.append(node)
        return self.odd_vertices
    def calculate_shortest_paths(self):
        """计算所有点对之间的最短路径"""
        return dict(nx.all_pairs_dijkstra_path_length(self.graph))
    def find_min_weight_matching(self, shortest_paths):
        """寻找最小权重完美匹配（暴力方法，适用于小规模）"""
        odd = self.odd_vertices
        n = len(odd)
        if n == 0:
            return [], 0
        # 生成所有可能的配对
        all_pairs = []
        for i in range(n):
            for j in range(i+1, n):
                all_pairs.append((odd[i], odd[j]))
        # 递归寻找最优匹配
        best_matching = None
        best_cost = float('inf')
        def find_matching(remaining, current_matching, current_cost):
            nonlocal best_matching, best_cost
            if not remaining:
                if current_cost < best_cost:
                    best_cost = current_cost
                    best_matching = current_matching[:]
                return
            # 选择第一个点
            first = remaining[0]
            remaining = remaining[1:]
            # 尝试与剩余所有点配对
            for i, second in enumerate(remaining):
                new_remaining = remaining[:i] + remaining[i+1:]
                cost = shortest_paths[first][second]
                new_matching = current_matching + [(first, second)]
                find_matching(new_remaining, new_matching, current_cost + cost)
        find_matching(odd, [], 0)
        return best_matching, best_cost
    def duplicate_edges(self, matching, shortest_paths):
        """添加重复边使图成为欧拉图"""
        for u, v in matching:
            path = nx.dijkstra_path(self.graph, u, v)
            # 在路径上添加重复边
            for i in range(len(path)-1):
                edge_data = self.graph.get_edge_data(path[i], path[i+1])
                self.graph.add_edge(path[i], path[i+1], 
                                   weight=edge_data['weight'],
                                   duplicated=True)
    def find_eulerian_circuit(self):
        """寻找欧拉回路"""
        # 确保是欧拉图
        try:
            self.eulerian_circuit = list(nx.eulerian_circuit(self.graph))
            return self.eulerian_circuit
        except nx.NetworkXError:
            print("图不是欧拉图")
            return []
    def solve(self, graph=None):
        """解决中国邮递员问题"""
        if graph is not None:
            self.graph = graph.copy()
        elif self.graph is None:
            self.graph = self.create_example_graph()
        print("=" * 50)
        print("中国邮递员问题求解")
        print("=" * 50)
        # 1. 找出奇度数顶点
        odd_vertices = self.find_odd_vertices()
        print(f"奇度数顶点: {odd_vertices}")
        if len(odd_vertices) > 0:
            # 2. 计算最短路径
            shortest_paths = self.calculate_shortest_paths()
            # 3. 寻找最小权重完美匹配
            matching, matching_cost = self.find_min_weight_matching(shortest_paths)
            print(f"最小匹配: {matching}")
            print(f"匹配总权重: {matching_cost}")
            # 4. 添加重复边
            self.duplicate_edges(matching, shortest_paths)
            # 5. 寻找欧拉回路
            circuit = self.find_eulerian_circuit()
            # 6. 计算总路径长度
            total_length = matching_cost
            for u, v, data in self.graph.edges(data=True):
                if not data.get('duplicated', False):
                    total_length += data['weight']
            print(f"总路径长度: {total_length}")
            return circuit, total_length
        else:
            # 已经是欧拉图
            circuit = self.find_eulerian_circuit()
            total_length = sum(self.graph[u][v]['weight'] for u, v in circuit)
            return circuit, total_length
    def visualize_graph(self, title="Chinese Postman Problem"):
        """可视化图"""
        plt.figure(figsize=(12, 8))
        pos = nx.spring_layout(self.graph, seed=42)
        # 绘制节点
        node_colors = ['red' if node in self.odd_vertices else 'lightblue' 
                      for node in self.graph.nodes()]
        nx.draw_networkx_nodes(self.graph, pos, node_color=node_colors, 
                              node_size=500, alpha=0.8)
        # 绘制边
        normal_edges = [(u, v) for u, v, d in self.graph.edges(data=True) 
                       if not d.get('duplicated', False)]
        duplicated_edges = [(u, v) for u, v, d in self.graph.edges(data=True) 
                          if d.get('duplicated', False)]
        nx.draw_networkx_edges(self.graph, pos, edgelist=normal_edges, 
                              width=2, alpha=0.7)
        nx.draw_networkx_edges(self.graph, pos, edgelist=duplicated_edges, 
                              width=2, alpha=0.5, 
                              edge_color='red', style='dashed')
        # 绘制边权重
        edge_labels = {(u, v): d['weight'] for u, v, d in self.graph.edges(data=True)}
        nx.draw_networkx_edge_labels(self.graph, pos, edge_labels, font_size=10)
        # 绘制节点标签
        nx.draw_networkx_labels(self.graph, pos, font_size=12, font_weight='bold')
        plt.title(title)
        plt.axis('off')
        # 添加图例
        from matplotlib.patches import Patch
        legend_elements = [
            Patch(facecolor='lightblue', label='Even degree vertex'),
            Patch(facecolor='red', label='Odd degree vertex'),
            plt.Line2D([0], [0], color='black', linewidth=2, label='Original edge'),
            plt.Line2D([0], [0], color='red', linewidth=2, linestyle='--', 
                      label='Duplicated edge')
        ]
        plt.legend(handles=legend_elements, loc='upper left')
        plt.tight_layout()
        plt.show()
    def visualize_solution(self, circuit, title="Eulerian Circuit"):
        """可视化欧拉回路"""
        if not circuit:
            print("没有找到欧拉回路")
            return
        plt.figure(figsize=(12, 8))
        pos = nx.spring_layout(self.graph, seed=42)
        # 绘制节点
        nx.draw_networkx_nodes(self.graph, pos, node_color='lightblue', 
                              node_size=500, alpha=0.8)
        nx.draw_networkx_labels(self.graph, pos, font_size=12, font_weight='bold')
        # 绘制边
        nx.draw_networkx_edges(self.graph, pos, width=2, alpha=0.3)
        # 绘制欧拉回路
        edge_colors = plt.cm.rainbow(np.linspace(0, 1, len(circuit)))
        for i, ((u, v), color) in enumerate(zip(circuit, edge_colors)):
            nx.draw_networkx_edges(self.graph, pos, 
                                  edgelist=[(u, v)], 
                                  edge_color=[color], 
                                  width=3, alpha=0.8)
        # 标记起点
        start_node = circuit[0][0]
        nx.draw_networkx_nodes(self.graph, pos, 
                              nodelist=[start_node], 
                              node_color='green', 
                              node_size=700, alpha=0.8)
        plt.title(title)
        plt.axis('off')
        # 添加颜色条表示路径顺序
        sm = plt.cm.ScalarMappable(cmap=plt.cm.rainbow, 
                                   norm=plt.Normalize(vmin=0, vmax=len(circuit)))
        sm.set_array([])
        plt.colorbar(sm, label='Step in circuit', shrink=0.8)
        plt.tight_layout()
        plt.show()
def main():
    # 创建求解器
    solver = ChinesePostmanSolver()
    # 示例1：使用预定义图
    print("\n示例1：预定义图")
    G1 = solver.create_example_graph()
    solver.graph = G1.copy()
    # 可视化原始图
    solver.visualize_graph("Original Graph")
    # 求解
    circuit, total_length = solver.solve(G1)
    if circuit:
        print(f"欧拉回路: {circuit}")
        print(f"访问顺序: ", end="")
        for u, v in circuit:
            print(f"{u}->{v} ", end="")
        print(f"\n总长度: {total_length}")
        # 可视化结果
        solver.visualize_solution(circuit, "Solution: Eulerian Circuit")
    # 示例2：使用随机图
    print("\n示例2：随机图")
    G2 = solver.create_random_graph(n_nodes=6, n_edges=10, seed=123)
    solver.graph = G2.copy()
    # 可视化原始图
    solver.visualize_graph("Random Graph")
    # 求解
    circuit2, total_length2 = solver.solve(G2)
    if circuit2:
        print(f"欧拉回路: {circuit2}")
        print(f"总长度: {total_length2}")
        # 可视化结果
        solver.visualize_solution(circuit2, "Solution: Eulerian Circuit (Random Graph)")
if __name__ == "__main__":
    main()

代码说明

核心算法步骤：

找出奇度数顶点
- 中国邮递员问题的关键是处理奇数度顶点
- 欧拉图中所有顶点度数必须为偶数
计算最短路径

使用Dijkstra算法计算所有奇度顶点对之间的最短路径
最小权重完美匹配
- 在奇度顶点之间找到最小总权重的配对
- 这样添加这些路径上的重复边后,所有顶点度数变为偶数
添加重复边
- 根据匹配结果,在最短路径上添加重复边
- 使图成为欧拉图
寻找欧拉回路

使用NetworkX的eulerian_circuit函数

关键函数：

find_odd_vertices(): 找出奇度数顶点
find_min_weight_matching(): 最小权重完美匹配
duplicate_edges(): 添加重复边
find_eulerian_circuit(): 寻找欧拉回路

运行结果示例：

==================================================
中国邮递员问题求解
==================================================
奇度数顶点: [0, 4, 5, 6]
最小匹配: [(0, 4), (5, 6)]
匹配总权重: 9
总路径长度: 42
欧拉回路: [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), ...]

这个实现包含了完整的中国邮递员问题解决方案,并提供了可视化功能，方便理解和调试。

本文地址： https://www.bmjup.com/post/22055.html