如何将大型图分割为独立的子图集群？

要把包含多个断开集群的大图拆成独立Graph对象，核心是识别图中的连通分量，再为每个分量生成新图。以下是具体实现方案：

核心思路 #

不管是有向图还是无向图，先找出所有相互连通的节点集群，再从原图中提取对应节点和边，创建独立的Graph对象。

具体步骤（以Python NetworkX库为例） #

1. 识别连通分量 #

• 无向图：用connected_components()获取所有连通节点集合
• 有向图：
  • 若忽略边的方向（如你示例中的链状结构），用weakly_connected_components()
  • 若只保留互相可达的强连通集群，用strongly_connected_components()

2. 生成独立子图 #

遍历每个连通节点集合，提取对应子图并复制为独立对象：

import networkx as nx

# 构建示例原图
G = nx.DiGraph()
G.add_edges_from([(1,2), (2,3), (10,20), (20,30)])

# 获取弱连通分量（对应示例中的两个断开集群）
components = list(nx.weakly_connected_components(G))

# 生成独立子图
subgraphs = []
for comp in components:
    sub_graph = G.subgraph(comp).copy()
    subgraphs.append(sub_graph)

# 输出验证
for idx, sg in enumerate(subgraphs, 1):
    print(f"子图{idx}的边：")
    print("\n".join(f"{u} -> {v}" for u, v in sg.edges()))
    print("---")

运行后会输出两个独立子图的边，和你要求的结果完全一致。

关于Roots属性的补充 #

你提到的Roots属性通常指入度为0的节点（常见于有向无环图DAG），也可以通过Root节点遍历可达节点来拆分图：

# 从Root节点（入度为0）遍历生成子图
roots = [node for node in G.nodes() if G.in_degree(node) == 0]
subgraphs_from_roots = []
for root in roots:
    reachable_nodes = nx.descendants(G, root) | {root}
    sub_graph = G.subgraph(reachable_nodes).copy()
    subgraphs_from_roots.append(sub_graph)

这种方法在DAG场景下同样有效，示例中的1和10都是Root节点，遍历后正好得到两个子图集群。

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