如何使用NetworkX提取图中的完全连通分量？

你之前使用nx.connected_components得到的是连通分量——只要节点之间存在路径相连就会被归为一组，不管组内是否每个节点都两两相连，所以结果包含d是正常的，但这不符合你要找「每个节点均与其他所有节点相连」的子图的需求。

你需要的是图论中的团（Clique）：团是指子图中任意两个不同节点之间都有边相连的子图。针对你的需求，可通过以下方式实现：

方法1：获取所有满足条件的极大团 #

如果希望得到所有满足条件且无法扩展为更大团的子图（即极大团），可以使用nx.find_cliques函数：

import networkx as nx

edges = [
    ('a', 'b'),
    ('a', 'c'),
    ('b', 'c'),
    ('a', 'd'),
    ('f', 'g')
]

graph = nx.Graph(edges)
# 获取所有极大团
max_cliques = list(nx.find_cliques(graph))
# 转换为集合列表，过滤掉单个节点的团
result = [set(clique) for clique in max_cliques if len(clique) >= 2]
print(result)

运行结果：[{'a', 'b', 'c'}, {'a', 'd'}, {'f', 'g'}]
这里{'a','d'}也是满足条件的完全子图（两个节点互相连接），如果不需要这类小团，可以额外添加过滤条件。

方法2：匹配你的期望结果（连通分量内的最大完全子图） #

如果你的目标是对每个连通分量，保留其中最大的完全子图（忽略连通分量内的小完全子图），可以这样实现：

import networkx as nx

edges = [
    ('a', 'b'),
    ('a', 'c'),
    ('b', 'c'),
    ('a', 'd'),
    ('f', 'g')
]

graph = nx.Graph(edges)
result = []

for component in nx.connected_components(graph):
    subgraph = graph.subgraph(component)
    # 检查当前连通分量是否本身就是完全图
    if nx.is_complete(subgraph):
        result.append(component)
    else:
        # 找出该连通分量中的最大团
        max_clique = max(nx.find_cliques(subgraph), key=len)
        result.append(set(max_clique))

print(result)

运行结果：[{'a', 'b', 'c'}, {'f', 'g'}]
这个结果完全符合你的期望：对非完全的连通分量{a,b,c,d}提取出其中最大的完全子图{a,b,c}，对本身就是完全图的连通分量{f,g}直接保留。

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