Python案例如何用Networkx做欧拉回路

wen python案例 2026-07-16 161

本文目录导读：

欧拉回路的基本概念
完整案例代码
关键函数说明
判断欧拉回路的条件

我来介绍如何使用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, "存在欧拉回路"

这个案例包含了完整的欧拉回路检测、可视化、分步演示和实际应用,希望对你有帮助！

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