如何用深度优先搜索（DFS）检测有向图中的多个重叠环？

嘿，我来帮你理清如何用改进的DFS找出有向图里的所有重叠环～你已经熟悉的WHITE/GREY/BLACK颜色标记是核心基础，我们只需要在这个基础上追踪当前递归路径，就能捕获所有重叠的环。

核心原理 #

常规DFS用颜色标记检测环的逻辑是：遇到灰色节点说明存在环，但要收集所有重叠环，我们需要额外维护一个当前路径栈，记录从起点到当前节点的完整路径：

• WHITE：节点未被访问过
• GREY：节点正在当前递归栈中（处于访问中）
• BLACK：节点已被完全处理（所有子节点都遍历完毕）
• 当遍历到一个灰色节点时，说明这个节点已经在当前路径里了——从该灰色节点到当前节点的路径，加上当前节点指向它的边，就是一个完整的环。
• 递归回溯时，要把当前节点从路径栈中移除，并标记为BLACK，这样才能探索其他分支的环（这也是能捕获重叠环的关键）。

伪代码 #

// 全局/类级变量
color[]: 每个节点的颜色，初始为WHITE
currentPath: 栈，记录当前递归路径中的节点
allCycles: 列表，存储所有找到的环

function dfs(node):
    color[node] = GREY
    push node to currentPath
    
    for each neighbor in adjacencyList[node]:
        if color[neighbor] == WHITE:
            dfs(neighbor)
        elif color[neighbor] == GREY:
            // 找到环：从neighbor到当前node的路径就是环
            cycle = 从currentPath中找到neighbor的位置，截取到当前node的部分，再加上neighbor
            add cycle to allCycles
    
    // 回溯：标记为已处理，移出当前路径
    color[node] = BLACK
    pop node from currentPath

// 启动遍历（假设图是连通的，若不连通则遍历所有未访问节点）
for each node in allNodes:
    if color[node] == WHITE:
        dfs(node)

针对你的场景说明 #

以你给出的图为例，当从节点1出发DFS时：

• 走到节点2后，会探索分支3和7，每一条分支遇到指向灰色节点（比如5指向1）时，就会截取路径生成环；
• 回溯后处理节点8的分支时，同样会捕获另外4个环，最终收集到全部8个重叠环。

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