如何使用NetworkX生成含N条边的所有连通及非连通无向图？

要生成含指定边数（如6条）的所有互不同构的无向图（包括连通和非连通类型），且支持任意边数，你可以通过遍历所有可能的节点数范围，结合NetworkX的nonisomorphic_graphs生成器来实现——因为NetworkX没有直接生成指定边数所有图的内置函数，需要组合节点数遍历+同构图生成来完成。

实现思路 #

对于E条边的无向图：

• 最小节点数n_min：满足n_min*(n_min-1)/2 >= E的最小整数（即该节点数的完全图能容纳下E条边）
• 最大节点数n_max：E+1（对应每个边都是独立的节点对，无共享节点的情况，比如E条边对应E+1个节点）

遍历n从n_min到n_max，生成每个节点数下E条边的所有非同构图，汇总后就是所有符合要求的图。

完整代码示例 #

import networkx as nx
import matplotlib.pyplot as plt
import math

def generate_all_graphs_with_edges(edge_count):
    # 计算最小节点数：满足n*(n-1)/2 >= edge_count的最小整数
    n_min = math.ceil((1 + math.sqrt(1 + 8 * edge_count)) / 2)
    # 最大节点数：每个边对应独立节点对，最多edge_count+1个节点
    n_max = edge_count + 1
    
    all_graphs = []
    for n in range(n_min, n_max + 1):
        # 生成n个节点、edge_count条边的所有非同构图
        graphs = nx.nonisomorphic_graphs(n, edges=edge_count)
        all_graphs.extend(graphs)
    
    return all_graphs

# 测试：生成6条边的所有无向图
E = 6
all_graphs = generate_all_graphs_with_edges(E)

# 遍历图，计算Weisfeiler-Lehman哈希并可视化
for idx, graph in enumerate(all_graphs):
    wl_hash = nx.weisfeiler_lehman_graph_hash(graph)
    print(f"图{idx+1}的WL哈希: {wl_hash}")
    
    plt.figure(idx+1, figsize=(4,4))
    nx.draw(graph, with_labels=True, node_color='lightblue', font_weight='bold')
    plt.title(f"图{idx+1} (节点数: {graph.number_of_nodes()}, 边数: {E})")

plt.show()

关键说明 #

1. nonisomorphic_graphs生成器：该函数会生成指定节点数和边数的所有互不同构的无向图，避免了重复生成同构的图。
2. 节点数范围计算：确保覆盖了所有可能存在E条边的无向图结构，不会遗漏任何情况。
3. 可视化与哈希计算：保留了你原代码中的WL哈希计算和Matplotlib可视化逻辑，方便验证图的唯一性。

注意：当边数E较大时，生成的图数量会呈指数级增长，因此该方法更适合处理较小的E值。

内容的提问来源于stack exchange，提问作者avgJoe