如何通过NetworkX获取METIS图分区的割边？是否需要遍历全部结果？

嘿，这两个问题都是图分区后常见的实操需求，我来给你拆解清楚：

核心逻辑其实很简单：割边的定义就是连接不同分区的边，所以只要拿到每个节点的分区标签，再对比每条边的两个端点所属分区是否不同就行。具体步骤如下：

1. 先用METIS完成图分区，得到每个分区的节点集合；
2. 把分区结果转换成「节点→分区ID」的字典，方便快速查询节点所属分区；
3. 遍历图中所有边，筛选出两端节点分区ID不同的边，这些就是割边。

给你个可直接运行的示例代码：

import networkx as nx
from networkx.algorithms.community import metis_partition

# 先构建/加载你的图，这里用空手道俱乐部图做示例
G = nx.karate_club_graph()

# 用METIS将图分成2个分区
partitions = metis_partition(G, 2)

# 构建节点到分区ID的映射字典
node_to_part = {}
for part_id, nodes in enumerate(partitions):
    for node in nodes:
        node_to_part[node] = part_id

# 遍历所有边，收集割边
cut_edges = []
for u, v in G.edges():
    if node_to_part[u] != node_to_part[v]:
        cut_edges.append((u, v))

print(f"找到的割边数量：{len(cut_edges)}")
print("割边列表：", cut_edges)

首先明确：不需要额外遍历所有分区结果，用和第一个问题完全一致的思路就能解决。已知割边数量为80只是一个验证指标，不影响获取割边的方法。具体步骤：

1. 执行METIS分区得到3个分区的节点集合，同样构建「节点→分区ID」的映射；
2. 遍历所有边，筛选出两端节点分区不同的边；
3. 最后可以验证收集到的割边数量是否为80，确认分区结果符合预期。

示例代码如下：

import networkx as nx
from networkx.algorithms.community import metis_partition

# 加载你的图（替换成你自己的图加载方式）
G = nx.read_edgelist("your_graph.edgelist")

# 分成3个分区
partitions = metis_partition(G, 3)

# 构建节点-分区ID映射
node_to_part = {}
for idx, part in enumerate(partitions):
    for node in part:
        node_to_part[node] = idx

# 收集割边
cut_edges = [(u, v) for u, v in G.edges() if node_to_part[u] != node_to_part[v]]

# 验证割边数量是否符合预期
assert len(cut_edges) == 80, f"实际割边数量为{len(cut_edges)}，与预期的80不符"

print("具体割边列表：", cut_edges)

为什么不用遍历所有分区？因为每个节点的分区ID已经明确了归属，直接对比边的两个节点ID是最直接高效的方式，时间复杂度为O(E)（E是图的边数），比两两对比分区之间的边要简单得多。

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