从“七桥问题”到快递路线规划：用Python NetworkX玩转图论基础概念

从“七桥问题”到快递路线规划：用Python NetworkX玩转图论基础概念

18世纪，普鲁士的哥尼斯堡城（现俄罗斯加里宁格勒）有一条河流经市区，河中有两座岛，七座桥连接着岛屿与河岸。当地居民热衷于思考一个问题：**能否设计一条路线，让人不重复地走遍所有七座桥？**这个看似简单的谜题，却难倒了无数人，直到数学家欧拉将其抽象为"图"的概念，开创了图论这一数学分支。

今天，图论早已从纯数学领域走向现实应用。从社交网络的好友推荐，到物流配送的最优路径规划；从电网的稳定性分析，到互联网数据包的路由选择——图论无处不在。本文将带你用Python的NetworkX库，重新演绎这段从七桥问题到现代应用的思维之旅。

1. 图论基础：从七桥问题到NetworkX建模

1.1 图的数学定义与现实对应

在图论中，一个**图(Graph)**由两部分组成：

• 顶点(Vertices)：表示实体（如快递网点、社交用户）
• 边(Edges)：表示实体间关系（如道路连接、好友关系）

七桥问题对应的图如下表示：

import networkx as nx # 创建无向图 konigsberg = nx.Graph() # 添加四个陆地区域作为顶点 land_areas = ['North', 'South', 'Island1', 'Island2'] konigsberg.add_nodes_from(land_areas) # 添加七座桥作为边 bridges = [('North', 'Island1'), ('North', 'Island1'), # 两座桥连接相同区域 ('North', 'Island2'), ('South', 'Island1'), ('South', 'Island2'), ('South', 'Island2'), ('Island1', 'Island2')] konigsberg.add_edges_from(bridges)

1.2 欧拉图的判定条件

欧拉当年证明七桥问题无解时，实际上建立了以下判定标准：

用NetworkX验证七桥图：

# 计算各顶点度数 degrees = dict(konigsberg.degree()) print(degrees) # 输出：{'North': 3, 'South': 3, 'Island1': 3, 'Island2': 3} # 判断是否存在欧拉回路 print(nx.is_eulerian(konigsberg)) # 输出：False

注意：现实中的道路系统通常需要同时考虑方向（单行道）和权重（距离/耗时），这时应使用有向带权图(DiGraph)建模。

2. 物流优化中的图论应用

2.1 快递路线规划与最短路径

假设某快递公司在城市有5个配送站，需要规划最优配送路线：

# 创建带权图表示配送网络 delivery = nx.Graph() delivery.add_weighted_edges_from([ ('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1), ('B', 'D', 5), ('C', 'D', 8), ('C', 'E', 10), ('D', 'E', 2) ]) # 计算A到E的最短路径 shortest_path = nx.shortest_path(delivery, 'A', 'E', weight='weight') path_length = nx.shortest_path_length(delivery, 'A', 'E', weight='weight') print(f"最短路径：{shortest_path}，总距离：{path_length}") # 输出：最短路径：['A', 'C', 'B', 'D', 'E']，总距离：10

2.2 多车配送与中国邮路问题

当需要多辆配送车时，问题转化为中国邮路问题——寻找覆盖所有边的最短闭合路径（可能重复经过某些边）。解法步骤：

1. 找出所有奇数度顶点（必为偶数个）
2. 将这些顶点配对，找出它们之间的最短路径
3. 在原图中复制这些最短路径上的边
4. 在新图中寻找欧拉回路

def chinese_postman(G): if nx.is_eulerian(G): return list(nx.eulerian_circuit(G)) # 找出奇数度顶点 odd_degree = [v for v, d in G.degree() if d % 2 == 1] # 计算所有奇数顶点对之间的最短路径 odd_pairs = nx.algorithms.matching.min_weight_matching( nx.Graph((u, v, {'weight': nx.shortest_path_length(G, u, v)}) for u in odd_degree for v in odd_degree if u != v)) # 复制边 G = G.copy() for u, v in odd_pairs: path = nx.shortest_path(G, u, v) for i in range(len(path)-1): G.add_edge(path[i], path[i+1]) return list(nx.eulerian_circuit(G)) # 应用示例 print(chinese_postman(delivery))

3. 网络健壮性分析与连通度

3.1 关键节点识别

在物流网络中，某些节点或连接线的故障可能导致整个系统瘫痪。图论提供了量化方法：

# 计算点连通度（最少需要删除多少个节点使图不连通） print(f"点连通度：{nx.node_connectivity(delivery)}") # 计算边连通度 print(f"边连通度：{nx.edge_connectivity(delivery)}") # 找出割点（删除后连通分支增加） print(f"割点：{list(nx.articulation_points(delivery))}")

3.2 增强网络可靠性

提高网络可靠性的常见策略：

• 增加冗余连接：使点/边连通度≥2
• 关键节点保护：为重要枢纽设计备用方案
• 分区设计：将网络划分为多个相对独立的子网

下表比较了不同网络拓扑的健壮性：

4. 高级应用：哈密顿回路与旅行商问题

4.1 哈密顿图与快递揽收路线

与欧拉回路不同，哈密顿回路要求访问每个顶点恰好一次。这直接对应著名的旅行商问题(TSP)：

# 生成完全图表示城市间距离 cities = ['A', 'B', 'C', 'D'] distances = {('A','B'):5, ('A','C'):10, ('A','D'):9, ('B','C'):6, ('B','D'):13, ('C','D'):4} # 使用近似算法求解 def tsp_approx(G): # 生成最小生成树 mst = nx.minimum_spanning_tree(G) # 前序遍历得到访问顺序 traversal = list(nx.dfs_preorder_nodes(mst, source='A')) # 添加起点形成环路 traversal.append(traversal[0]) # 计算总距离 total = sum(G[u][v]['weight'] for u,v in zip(traversal[:-1], traversal[1:])) return traversal, total tsp_graph = nx.Graph() for edge, weight in distances.items(): tsp_graph.add_edge(edge[0], edge[1], weight=weight) path, dist = tsp_approx(tsp_graph) print(f"近似最优路径：{path}，总距离：{dist}")

4.2 现实中的复杂约束

实际物流问题还需考虑：

• 时间窗口限制
• 车辆载重容量
• 动态交通状况
• 多仓库协同

这些可以通过扩展基本图模型来实现：

# 添加时间窗属性 for node in tsp_graph.nodes: tsp_graph.nodes[node]['time_window'] = (8, 20) # 8:00-20:00可访问 # 添加需求属性 demands = {'A':2, 'B':3, 'C':1, 'D':4} nx.set_node_attributes(tsp_graph, demands, 'demand') # 车辆容量 vehicle_capacity = 5

在解决实际项目中的物流优化问题时，我发现最耗时的往往不是算法本身，而是数据的清洗和预处理。确保顶点和边的属性完整准确，比选择哪种优化算法更重要。例如，某次因道路施工数据未及时更新，导致计算的最优路径实际无法通行，这个教训让我建立了严格的数据验证流程。