Python案例如何用Networkx做图的周长

wen python案例 2026-07-15 184

本文目录导读：

基本概念
实现方法
不同图类型的周长示例
高级应用：计算图的周长分布
性能优化和注意事项

我来为您详细介绍如何使用NetworkX计算图的周长（图论中的周长是指图中最短环的长度）。

基本概念

图的周长（Girth）是指图中最短环（cycle）的长度，如果图是无环的,则周长定义为无穷大。

实现方法

使用NetworkX内置函数

import networkx as nx
import matplotlib.pyplot as plt
# 创建一个示例图
G = nx.Graph()
# 添加边来形成环
edges = [(1, 2), (2, 3), (3, 4), (4, 1),  # 4-cycle
         (3, 5), (5, 6), (6, 3)]  # 3-cycle
G.add_edges_from(edges)
# 计算周长
girth = nx.girth(G)
print(f"图的周长是: {girth}")
# 可视化图
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', 
        node_size=500, font_size=16, font_weight='bold')
nx.draw_networkx_edge_labels(G, pos, edge_labels={(u,v): f'{u}-{v}' for u,v in G.edges()})f"图周长: {girth}")
plt.show()

手动实现周长计算

import networkx as nx
from collections import deque
import math
def compute_girth_manual(G):
    """
    手动计算图的周长
    """
    if not nx.is_connected(G):
        return float('inf')
    min_cycle_length = float('inf')
    for node in G.nodes():
        # BFS找到最短环
        dist = {node: 0}
        parent = {node: None}
        queue = deque([node])
        while queue:
            current = queue.popleft()
            for neighbor in G.neighbors(current):
                if neighbor not in dist:
                    dist[neighbor] = dist[current] + 1
                    parent[neighbor] = current
                    queue.append(neighbor)
                elif neighbor != parent[current]:
                    # 找到一个环
                    cycle_length = dist[current] + dist[neighbor] + 1
                    min_cycle_length = min(min_cycle_length, cycle_length)
    return min_cycle_length if min_cycle_length != float('inf') else float('inf')
# 使用示例
G = nx.petersen_graph()  # 著名的彼得森图
manual_girth = compute_girth_manual(G)
networkx_girth = nx.girth(G)
print(f"手动计算的周长: {manual_girth}")
print(f"NetworkX计算的周长: {networkx_girth}")

查找所有环并找最短的

import networkx as nx
def find_shortest_cycle(G):
    """
    查找图中所有环并找出最短的
    """
    # 查找所有简单环
    try:
        all_cycles = list(nx.simple_cycles(G))
        if not all_cycles:
            return float('inf'), None
        # 找到最短环
        shortest_cycle = min(all_cycles, key=len)
        return len(shortest_cycle), shortest_cycle
    except nx.NetworkXNoCycle:
        return float('inf'), None
# 使用示例
G = nx.Graph()
G.add_edges_from([(1,2), (2,3), (3,4), (4,1), (2,5), (5,6), (6,2)])
# 注意：simple_cycles只适用于有向图
G_directed = nx.DiGraph(G)
girth_value, shortest_cycle = find_shortest_cycle(G_directed)
if shortest_cycle:
    print(f"最短环长度: {girth_value}")
    print(f"最短环路径: {shortest_cycle}")
else:
    print("图中没有环")

不同图类型的周长示例

import networkx as nx
import matplotlib.pyplot as plt
def analyze_graph_types():
    """分析不同类型的图的周长"""
    # 1. 完全图 K5
    K5 = nx.complete_graph(5)
    print(f"K5的周长: {nx.girth(K5)}")  # 应该为3
    # 2. 环图 C6
    C6 = nx.cycle_graph(6)
    print(f"C6的周长: {nx.girth(C6)}")  # 应该为6
    # 3. 树（无环）
    tree = nx.balanced_tree(2, 3)
    print(f"树的周长: {nx.girth(tree)}")  # 应该为inf
    # 4. 网格图
    grid = nx.grid_2d_graph(3, 3)
    print(f"3x3网格图的周长: {nx.girth(grid)}")  # 应该为4
    # 5. 社交网络图
    karate = nx.karate_club_graph()
    print(f"空手道俱乐部图周长: {nx.girth(karate)}")
    # 可视化
    fig, axes = plt.subplots(2, 3, figsize=(15, 10))
    graphs = [K5, C6, tree, grid, karate]s = [f"K5 (周长: {nx.girth(K5)})",
              f"C6 (周长: {nx.girth(C6)})",
              f"树 (周长: {nx.girth(tree)})",
              f"网格图 (周长: {nx.girth(grid)})",
              f"空手道图 (周长: {nx.girth(karate)})"]
    for ax, G, title in zip(axes.flat, graphs, titles):
        pos = nx.spring_layout(G) if not isinstance(G, nx.GridGraph) else nx.grid_2d_graph(3,3).nodes()
        nx.draw(G, pos, ax=ax, with_labels=True, node_color='lightblue', 
                node_size=100, font_size=8)
        ax.set_title(title)
    plt.tight_layout()
    plt.show()
analyze_graph_types()

高级应用：计算图的周长分布

import networkx as nx
from collections import Counter
def cycle_length_distribution(G, max_length=10):
    """
    计算图中不同长度环的分布
    """
    cycle_lengths = []
    # 对于小的图，可以枚举所有环
    if G.number_of_nodes() <= 20:
        try:
            all_cycles = nx.cycle_basis(G)
            for cycle in all_cycles:
                length = len(cycle)
                if length <= max_length:
                    cycle_lengths.append(length)
        except:
            pass
    # 统计分布
    distribution = Counter(cycle_lengths)
    return distribution
# 使用示例
G = nx.dodecahedral_graph()  # 十二面体图
distribution = cycle_length_distribution(G)
print("环长度分布:")
for length, count in sorted(distribution.items()):
    print(f"  长度 {length}: {count} 个环")
# 可视化环长分布
import matplotlib.pyplot as plt
plt.figure(figsize=(10, 6))
lengths = sorted(distribution.keys())
counts = [distribution[l] for l in lengths]
plt.bar(lengths, counts, color='skyblue', edgecolor='black')
plt.xlabel('环的长度')
plt.ylabel('环的数量')'图的环长度分布')
plt.xticks(lengths)
plt.grid(True, alpha=0.3)
plt.show()

性能优化和注意事项

import networkx as nx
import time
def compare_performance():
    """比较不同方法的性能"""
    # 生成一个中等大小的随机图
    G = nx.erdos_renyi_graph(100, 0.1)
    # 方法1: 使用内置函数
    start = time.time()
    girth1 = nx.girth(G)
    time1 = time.time() - start
    # 方法2: 使用BFS手动计算
    start = time.time()
    girth2 = compute_girth_manual(G)
    time2 = time.time() - start
    print(f"内置函数: 周长={girth1}, 时间={time1:.4f}秒")
    print(f"手动BFS: 周长={girth2}, 时间={time2:.4f}秒")
    print(f"结果一致: {girth1 == girth2}")
# 注意事项函数
def girth_notes():
    """
    使用NetworkX计算周长时的注意事项
    """
    notes = """
    1. 无环图: nx.girth() 返回 inf (无穷大)
    2. 有向图: nx.girth() 会考虑边的方向
    3. 多图: 如果有平行边，最小环可能是2
    4. 大规模图: 计算周长可能很耗时
    5. 连通性: 非连通图的周长可能不可靠
    """
    print(notes)
    # 示例：各种特殊情况
    print("特殊案例:")
    # 无环图
    tree = nx.path_graph(5)
    print(f"  路径图(无环): {nx.girth(tree)}")
    # 有平行边的图
    multigraph = nx.MultiGraph()
    multigraph.add_edges_from([(1,2), (1,2), (2,3), (3,1)])
    print(f"  多重图: {nx.girth(multigraph)}")
    # 不连通图
    disconnected = nx.Graph()
    disconnected.add_cycle([1,2,3])
    disconnected.add_cycle([4,5,6,7])
    print(f"  不连通图: {nx.girth(disconnected)}")
# 运行性能比较
compare_performance()
girth_notes()

这些代码展示了使用NetworkX计算图周长的多种方法，从基础到高级应用,根据您的具体需求选择合适的方法即可。

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