如何用NetworkX生成含n个节点的所有不同图结构？

方法一：利用NetworkX内置图集（推荐，适用于n≤7） #

NetworkX提供了graph_atlas_g()函数，返回所有节点数≤7的非同构图集合（即结构唯一的图），直接筛选目标节点数的图即可：

import networkx as nx

n = 4
# 从图集中筛选节点数为n的所有唯一图
all_unique_graphs = [G for G in nx.graph_atlas_g() if G.number_of_nodes() == n]

# 验证结果：n=4时应返回11个图
print(f"节点数为{n}的唯一图数量：{len(all_unique_graphs)}")

这个方法无需手动处理同构判断，图集里的图已经是去重后的结果，效率极高。

方法二：手动生成并去重（适用于n>7或自定义场景） #

如果节点数超过7，图集未覆盖，可以通过生成所有可能的边组合，再用同构判断去重：

import networkx as nx
from itertools import combinations

n = 4
nodes = list(range(n))
all_possible_edges = list(combinations(nodes, 2))
unique_graphs = []

# 遍历所有边的子集（从0条边到全连接）
for edge_count in range(len(all_possible_edges) + 1):
    for edge_subset in combinations(all_possible_edges, edge_count):
        # 创建当前图
        current_graph = nx.Graph()
        current_graph.add_nodes_from(nodes)
        current_graph.add_edges_from(edge_subset)
        
        # 检查是否已存在同构图
        is_unique = True
        for existing_graph in unique_graphs:
            if nx.is_isomorphic(current_graph, existing_graph):
                is_unique = False
                break
        if is_unique:
            unique_graphs.append(current_graph)

print(f"节点数为{n}的唯一图数量：{len(unique_graphs)}")

注意：这种方法时间复杂度随节点数指数增长，仅适合小n场景。判断同构的核心函数是nx.is_isomorphic()，它会对比图的结构特征确保唯一性。

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