NetworkX图中枚举团仅得1/2阶，如何查找图中的环路？

我使用NetworkX创建了一个连通图，尝试调用该包的enumerate_all_cliques()方法查找所有团，但仅得到大小为1和2的团。

不过我在图中发现存在26-37-36-35-34-33-32-31-30-29-28-27-26这样的闭合环路。

我刚接触图论，不确定上述结构是否属于团，想了解如何查找图中所有这类起点与终点相同的环路？

团和闭合环路的区别 #

你说的这个闭合环路不是团。图论里的团要求子图内任意两个不同顶点之间都有直接边相连，而你的环路只有相邻顶点间有边——比如26和36之间根本没有直接边，完全不符合团的定义，这就是enumerate_all_cliques()只返回大小1和2的团的原因：你的图里没有更大的团。

用NetworkX查找闭合环路的方法 #

根据你要找的环的类型，有不同的处理方式：

• 找顶点不重复的简单环：用simple_cycles()方法，但这个方法仅支持有向图。如果你的图是无向图，先把每个无向边拆成两条反向的有向边转成有向图，再调用该方法。另外find_cycle()能找到单个环，但只会返回一个结果。
• 找允许重复顶点的环：NetworkX没有直接的内置函数，得自己用深度优先搜索（DFS）写逻辑——记录走过的路径，当回到起点时就把这条路径存下来。

给个无向图找简单环的代码示例：

import networkx as nx

# 假设你的无向图是G，先构建好你的图
G = nx.Graph()
# 这里添加你的图的边...

# 转成有向图
digraph = nx.DiGraph(G)
# 获取所有简单环
cycles = list(nx.simple_cycles(digraph))

# 无向图的环会正反各出现一次，这里做去重处理
unique_cycles = []
seen = set()
for cycle in cycles:
    # 只保留长度大于2的环（排除两个顶点的重复边）
    if len(cycle) > 2:
        # 把环转成标准化的形式来判重
        sorted_cycle = tuple(sorted(cycle))
        if sorted_cycle not in seen:
            seen.add(sorted_cycle)
            unique_cycles.append(cycle)

print(unique_cycles)

注意：如果图的规模较大，枚举所有环的计算量会特别大，因为环的数量可能呈指数级增长。

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