如何用Python找出图中两组顶点之间的割边？

编程语言 2026-07-10

我正在使用NetworkX处理一个包含11个节点的图（代表朋友）。我手动把这个图分成两个组，我想找出连接这两组的边，即割边。

这是我的代码：

import networkx as nx  

G = nx.Graph()  

edges = [
    (1,2),(1,3),(2,3),  
    (4,5),(5,6),(4,6),  
    (7,8),(8,9),(9,7),  
    (10,11),  
    (3,4),(6,7),(9,10)  
]  

G.add_edges_from(edges)  

group1 = {1,2,3,4,5}  
group2 = {6,7,8,9,10,11}  

cuts = []  

for u, v in G.edges():  
    if (u in group1 and v in group2) or (u in group2 and v in group1):  
        cuts.append((u, v))  

print(cuts)

这会得到两组之间的割边。

我的问题是：

这是找到割边的正确方法吗？
NetworkX是否有内置函数可以更高效地完成这项工作？
如何让分区自动平衡，而不是手动定义分组？

我想找到最小割（最佳分区），而不是手动选择分组。

解决方案

regarding your questions:

这是以O(E) 时间复杂度实现的正确方法，因为集合中的 in 由于哈希表的原因，查找为O(1)。
NetworkX有许多内置函数，例如 edge_boundary(G1, group1, group2)，你可以在代码中使用它们：

```py import networkx as nx

G = nx.Graph() edges = [(1, 2), (1, 3), (2, 3), (4, 5), (5, 6), (4, 6), (7, 8), (8, 9), (9, 7), (10, 11), (3, 4), (6, 7), (9, 10)] G.add_edges_from(edges)

group1 = {1, 2, 3, 4, 5} group2 = {6, 7, 8, 9, 10, 11}

cut_edges = list(nx.edge_boundary(G, group1, group2)) print(cut_edges) ``` 3.要自动找到平衡的分区，请使用图分区算法

最大流-最小割定理、 Stoer–Wagner算法的最小割和多级分区（METIS）

Python