本文目录导读：
我来介绍如何使用NetworkX实现欧拉回路的案例。
欧拉回路的基本概念
欧拉回路是经过图中每条边恰好一次，最后回到起点的路径,判断条件：
- 无向图：所有顶点度数均为偶数
- 有向图：每个顶点的入度等于出度
完整案例代码
import networkx as nx
import matplotlib.pyplot as plt
def find_eulerian_circuit():
"""查找并可视化欧拉回路"""
# 方法1：创建满足欧拉回路条件的图
G = nx.Graph()
# 添加边构造一个欧拉图（所有节点度数为偶数）
edges = [
('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'A'), # 四边形
('A', 'C'), ('B', 'D') # 对角线
]
G.add_edges_from(edges)
# 检查图是否存在欧拉回路
print("=== 检查是否满足欧拉回路条件 ===")
print(f"节点数量: {G.number_of_nodes()}")
print(f"边数量: {G.number_of_edges()}")
# 检查连通性
print(f"是否连通: {nx.is_connected(G)}")
# 检查所有节点度数
all_even = all(d % 2 == 0 for node, d in G.degree())
print(f"所有节点度数为偶数: {all_even}")
if all_even and nx.is_connected(G):
print("\n✓ 存在欧拉回路！")
# 查找欧拉回路
euler_circuit = list(nx.eulerian_circuit(G))
print(f"\n欧拉回路路径:")
for i, (u, v) in enumerate(euler_circuit, 1):
print(f"第{i}步: {u} -> {v}")
return G, euler_circuit
else:
print("\n✗ 不存在欧拉回路")
return None, None
def create_eulerian_graph():
"""创建一个确保有欧拉回路的图"""
# 使用更复杂的方式构建
G = nx.Graph()
# 添加节点
nodes = ['1', '2', '3', '4', '5', '6']
G.add_nodes_from(nodes)
# 确保所有节点度数为偶数
edges = [
('1', '2'), ('2', '3'), ('3', '1'), # 三角形1
('4', '5'), ('5', '6'), ('6', '4'), # 三角形2
('2', '5'), ('3', '4'), ('1', '6') # 连接边
]
G.add_edges_from(edges)
return G
def visualize_eulerian_circuit(G, euler_circuit):
"""可视化欧拉回路"""
plt.figure(figsize=(12, 8))
# 设置布局
pos = nx.spring_layout(G, seed=42)
# 绘制图
nx.draw_networkx_nodes(G, pos, node_color='lightblue',
node_size=500, alpha=0.8)
nx.draw_networkx_labels(G, pos, font_size=12, font_weight='bold')
# 先绘制普通边
nx.draw_networkx_edges(G, pos, edge_color='gray',
style='dashed', alpha=0.5)
# 绘制欧拉回路路径（带箭头）
for i, (u, v) in enumerate(euler_circuit):
# 标记路径顺序
plt.annotate(f'{i+1}',
xy=((pos[u][0] + pos[v][0])/2,
(pos[u][1] + pos[v][1])/2),
ha='center', va='center',
bbox=dict(boxstyle='circle', facecolor='yellow',
edgecolor='black'),
fontsize=10, fontweight='bold')
# 绘制路径边
nx.draw_networkx_edges(G, pos, edgelist=[(u, v)],
edge_color='red', width=2)
plt.title("欧拉回路可视化（黄色数字表示路径顺序）", fontsize=14)
plt.axis('off')
plt.tight_layout()
plt.show()
def eulerian_circuit_with_animation(G, euler_circuit):
"""分步显示欧拉回路"""
print("\n=== 欧拉回路分步演示 ===")
pos = nx.spring_layout(G, seed=42)
plt.figure(figsize=(10, 8))
# 绘制基础图
nx.draw_networkx_nodes(G, pos, node_color='lightgreen',
node_size=500, alpha=0.8)
nx.draw_networkx_labels(G, pos, font_size=12, font_weight='bold')
nx.draw_networkx_edges(G, pos, edge_color='gray',
style='dashed', alpha=0.3)
# 分步显示
visited_edges = []
current_node = euler_circuit[0][0]
print(f"起始节点: {current_node}")
for i, (u, v) in enumerate(euler_circuit, 1):
visited_edges.append((u, v))
# 绘制已访问的边
nx.draw_networkx_edges(G, pos, edgelist=visited_edges,
edge_color='red', width=2)
# 标记当前节点
nx.draw_networkx_nodes(G, pos, nodelist=[current_node],
node_color='yellow', node_size=600)
current_node = v
# 添加路径信息
plt.title(f"欧拉回路 - 第{i}步: {u} -> {v}", fontsize=14)
if i == len(euler_circuit):
plt.title(f"欧拉回路完成! 回到起点 {v}", fontsize=14)
plt.axis('off')
plt.pause(0.5)
plt.show()
def practical_example():
"""实际应用案例：邮差送信路线"""
print("\n=== 实际应用：邮差送信路线规划 ===")
# 创建街道网络图
G = nx.Graph()
# 街道交叉口
intersections = ['A', 'B', 'C', 'D', 'E', 'F']
# 街道（确保是欧拉图）
streets = [
('A', 'B', {'street': '主街', 'length': 100}),
('B', 'C', {'street': '东街', 'length': 150}),
('C', 'D', {'street': '南街', 'length': 120}),
('D', 'A', {'street': '西街', 'length': 130}),
('A', 'E', {'street': '中央街', 'length': 80}),
('B', 'F', {'street': '北街', 'length': 90}),
('E', 'F', {'street': '环城路', 'length': 200}),
('C', 'F', {'street': '新区路', 'length': 110}),
('D', 'E', {'street': '老城路', 'length': 95})
]
G.add_edges_from(streets)
# 检查欧拉回路
if all(d % 2 == 0 for n, d in G.degree()):
euler_circuit = list(nx.eulerian_circuit(G))
print("邮差最优路线:")
total_length = 0
for i, (u, v) in enumerate(euler_circuit, 1):
length = G[u][v]['length']
total_length += length
street_name = G[u][v]['street']
print(f"{i}. {u} -> {v} （{street_name}，{length}米）")
print(f"\n总路线长度: {total_length}米")
# 可视化
plt.figure(figsize=(10, 8))
pos = nx.spring_layout(G, seed=42, k=2)
# 绘制街道网络
nx.draw_networkx_nodes(G, pos, node_color='lightblue',
node_size=800, alpha=0.8)
nx.draw_networkx_labels(G, pos, font_size=14, font_weight='bold')
# 绘制所有街道
nx.draw_networkx_edges(G, pos, edge_color='gray',
style='dashed', alpha=0.5)
# 绘制欧拉回路
nx.draw_networkx_edges(G, pos, edgelist=euler_circuit,
edge_color='red', width=2.5)
plt.title("邮差最优送信路线（红色：欧拉回路）", fontsize=14)
plt.axis('off')
plt.tight_layout()
plt.show()
# 主程序
if __name__ == "__main__":
print("NetworkX 欧拉回路案例分析")
print("=" * 40)
# 1. 基本欧拉回路
G, circuit = find_eulerian_circuit()
if circuit:
# 2. 可视化
visualize_eulerian_circuit(G, circuit)
# 3. 分步演示
eulerian_circuit_with_animation(G, circuit)
# 4. 构建自定义欧拉图
G2 = create_eulerian_graph()
print(f"\n自定义欧拉图 - 节点数: {G2.number_of_nodes()}, 边数: {G2.number_of_edges()}")
# 5. 实际应用案例
practical_example()
print("\n程序运行完成！")
关键函数说明
nx.eulerian_circuit(G): 查找欧拉回路的核心函数nx.is_connected(G): 检查图的连通性G.degree(): 获取节点度数
判断欧拉回路的条件
def check_eulerian_condition(G):
"""检查欧拉回路条件"""
# 检查连通性
if not nx.is_connected(G):
return False, "图不连通"
# 检查度数
odd_degree_nodes = [n for n, d in G.degree() if d % 2 != 0]
if odd_degree_nodes:
return False, f"奇数度节点: {odd_degree_nodes}"
return True, "存在欧拉回路"
这个案例包含了完整的欧拉回路检测、可视化、分步演示和实际应用,希望对你有帮助！
