环路检测的 DFS 算法

传统的 DFS 算法比较简单，这里考虑可以进行环路检测的 DFS 算法, 该算法也称为 “White-Gray-Black” DFS。

算法思路

对于访问的节点，相比于以往使用 visited 数组记录一个点是否访问，这里使用一个 color 数组，将状态分为三种：

1. WHITE: 节点还未访问
2. GRAY: 节点正在被访问
3. BLACK: 节点已经访问

可以看到，节点正在访问的情况也被记录，如果再一次搜索中，一个节点正在被访问 ( 节点的 color 已经是灰色 ) 时，又一次被访问，则说明该节点在环中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 返回 false 如果有环。
const cycleDFS = idx => {
    // WHITE - 0 | GRAY - 1 | BLACK - 2
    // 正在遍历标记为 GRAY
    color[idx] = 1;
    for (const v of g[idx]) {
        // BLACK 节点直接忽略
        if (color[v] === 2) continue;
        // v 是 GRAY，说明环路了 
        // 或
        // v 是 WHITE 并递归检测下这个节点，如果 dfs 返回 false，说明有环
        // 其中一个成立本函数返回 false
        if (color[v] === 1 || !cycleDFS(v)) {
            return false;
        }
    }
    // 该节点检查完毕，置为 BLACK
    color[idx] = 2;
    // 之前都没找到回路，这里就返回 true
    return true;
}

小结

本文对环路检测的算法 “White-Gray-Black” DFS 进行了简单的记录，总的来说，相较于普通的 DFS 算法，该算法将 visited 数组的状态进行了扩展，使得算法可以区分一个节点的正在访问状态。于是可以判定一个节点在一个路径上是否出现了两次 ( 如果一个节点正在访问且又一次访问到了该节点，说明该节点在一个环上 )。

总的来说，对于环路检测问题，已知有以下思路：

1. 拓扑排序 (不停去掉入度为 0 的节点，如果最后还有节点无法去除，说明有环)
2. "White-Gray-Black" DFS (检测一个 visiting 的节点是否又一次被 visit)
3. 链表环路检测算法 ( 是两个指针以不同的速度前进，如果相遇说明遇到环路 )
4. …

以上方法应该在需要的时候灵活使用。

• ← Previous Post
• Next Post →