本文目录导读：
我来为您详细介绍如何使用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计算图周长的多种方法，从基础到高级应用,根据您的具体需求选择合适的方法即可。
