Python遍历邻接矩阵所有环：解决现有代码遗漏环的问题

问题分析 #

现有代码只能识别基础环，无法捕获包含多个小环的复合环，核心缺陷包括：

• 全局变量temp和t在递归中状态混乱，无法独立维护每条路径
• 找到环后直接返回，未做回溯探索其他分支
• 用列表记录递归状态的方式过于死板，限制了重复经过起点（但不重复完整路径）的复合环探索

修复后的代码 #

mat = [[0,1,0,1,0] , [0,0,1,0,0] , [1,0,0,0,0] , [0,0,0,0,1] , [1,0,0,0,0]]

def find_all_cycles(mat):
    node_count = len(mat)
    visited = [False] * node_count
    unique_cycles = set()  # 用集合自动去重，避免重复环

    def dfs(current_node, start_node, path):
        # 回到起点且路径非空，记录这个环
        if current_node == start_node and len(path) > 0:
            unique_cycles.add(tuple(path))
            return
        visited[current_node] = True
        # 遍历所有邻接节点
        for neighbor in range(node_count):
            if mat[current_node][neighbor]:
                if not visited[neighbor]:
                    path.append(f"{current_node+1} -> {neighbor+1}")
                    dfs(neighbor, start_node, path)
                    path.pop()  # 回溯，探索其他分支
                elif neighbor == start_node and len(path) > 1:
                    # 允许回到起点，形成跨多个小环的复合路径
                    path.append(f"{current_node+1} -> {neighbor+1}")
                    dfs(neighbor, start_node, path)
                    path.pop()
        visited[current_node] = False

    # 以每个节点为起点，遍历所有可能的环
    for start in range(node_count):
        dfs(start, start, [])
        visited = [False] * node_count

    # 打印所有环
    for cycle in unique_cycles:
        print(list(cycle))

# 执行函数
find_all_cycles(mat)

逻辑说明 #

• 用局部路径变量替代全局变量，通过回溯操作维护每条路径的独立状态
• 集合存储环的元组，自动过滤重复的环（如方向相反但节点序列一致的环）
• 调整DFS规则：允许路径长度大于1时回到起点，以此捕获复合环
• 每个起点单独初始化访问状态，确保所有可能的环都被遍历到
• 无环场景下集合为空，不会产生输出

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