如何在仅含父节点信息的有向图中检测环（无需转换结构）

核心思路 #

你的图中每个节点存储的是父节点列表（边方向为：当前节点 → 父节点），环的本质是从某个节点出发，沿着父节点路径递归遍历后能回到自身。我们可以用带路径跟踪的DFS实现环检测，完全不需要转换图结构。

具体实现步骤 #

1. 维护两个集合：
   • visited：记录已完全遍历的节点，避免重复处理
   • current_path：记录当前DFS路径中的节点，用于实时检测环
2. 遍历图中所有节点，若节点未被访问则启动DFS：
   • 若当前节点已在current_path中，说明找到环
   • 否则将节点加入current_path，递归遍历其所有父节点
   • 父节点遍历完成后，将节点从current_path移除并加入visited

代码实现 #

class Node:
    def __init__(self, name, parents):
        self.name = name
        self.parents = parents

def has_cycle(graph):
    visited = set()
    current_path = set()
    # 建立节点名称到对象的映射，快速查找父节点
    node_map = {node.name: node for node in graph}

    def dfs(node):
        if node.name in visited:
            return False
        if node.name in current_path:
            return True
        
        current_path.add(node.name)
        # 遍历所有父节点
        for parent_name in node.parents:
            parent_node = node_map.get(parent_name)
            if not parent_node:
                continue  # 可根据业务需求处理父节点不存在的情况
            if dfs(parent_node):
                return True
        
        current_path.remove(node.name)
        visited.add(node.name)
        return False

    # 逐个检查节点
    for node in graph:
        if dfs(node):
            return True
    return False

# 测试无环图
acyclic_graph = [Node("source", []), Node("node1", ["source"]), Node("node2", ["node1", "source"])]
print(has_cycle(acyclic_graph))  # 输出: False

# 测试有环图
cyclic_graph = [Node("source", []), Node("node1", ["source", "node3"]), Node("node2", ["node1"]), Node("node3", ["node1"])]
print(has_cycle(cyclic_graph))  # 输出: True

关键说明 #

• 无需转换图结构：直接利用节点自带的父节点列表遍历，无需构建反向邻接表
• 路径跟踪：current_path是检测环的核心，能捕捉到递归过程中回到路径内节点的情况
• 效率优化：visited集合避免重复处理已确认无环的节点，减少冗余递归

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