本文目录导读：
我来为你详细讲解如何使用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), ...]这个实现包含了完整的中国邮递员问题解决方案,并提供了可视化功能，方便理解和调试。
