如何使用 DFS 的迭代版本检测有向图中的循环？

Question

在递归 DFS 中，我们可以通过将节点着色为 WHITE、GRAY 和 BLACK 来检测循环，如 here 所述。

如果在DFS搜索过程中遇到GRAY个节点，则存在循环。

我的问题是：在这个迭代版本的 DFS 中什么时候将节点标记为 GRAY 和 BLACK？（来自维基百科）

    1  procedure DFS-iterative(G,v):
    2      let S be a stack
    3      S.push(v)
    4      while S is not empty
    5          v = S.pop()
    6          if v is not labeled as discovered:
    7              label v as discovered
    8              for all edges from v to w in G.adjacentEdges(v) do 
    9                  S.push(w)

Answer 1

在DFS中，分支的末端是没有children的节点，这些节点是Black。然后检查了 parent 个这些节点。如果 parent 没有 Gray child 那么它就是 Black。同样，如果继续给节点设置黑色，则所有节点的颜色都变成黑色。

例如，我想在下图中执行DFS。

DFS 从 u 开始，访问了 u -> v -> y -> x。 x 没有 children，您应该将此节点的颜色更改为 Black。

然后根据discovery time访问的路径中x的return到parent。所以 x 的 parent 是 y。 y 没有具有 Gray 颜色的 children，因此您应该将此节点的颜色更改为 Black。

Answer 2

一个选项是，如果您要进入或退出信息，则将每个节点两次推送到堆栈中。当您从堆栈中弹出一个节点时，您会检查您是进入还是退出。如果输入颜色为灰色，将其再次推入堆叠并前进到邻居。如果退出，只需将其涂成黑色。

这是一个简短的 Python 演示，可检测简单图形中的循环：

from collections import defaultdict

WHITE = 0
GRAY = 1
BLACK = 2

EDGES = [(0, 1), (1, 2), (0, 2), (2, 3), (3, 0)]

ENTER = 0
EXIT = 1

def create_graph(edges):
    graph = defaultdict(list)
    for x, y in edges:
        graph[x].append(y)

    return graph

def dfs_iter(graph, start):
    state = {v: WHITE for v in graph}
    stack = [(ENTER, start)]

    while stack:
        act, v = stack.pop()

        if act == EXIT:
            print('Exit', v)
            state[v] = BLACK
        else:
            print('Enter', v)
            state[v] = GRAY
            stack.append((EXIT, v))
            for n in graph[v]:
                if state[n] == GRAY:
                    print('Found cycle at', n)
                elif state[n] == WHITE:
                    stack.append((ENTER, n))

graph = create_graph(EDGES)
dfs_iter(graph, 0)

输出：

Enter 0
Enter 2
Enter 3
Found cycle at 0
Exit 3
Exit 2
Enter 1
Exit 1
Exit 0

Answer 3

您可以通过不立即弹出堆栈元素来做到这一点。对于每次迭代，执行 v = stack.peek() 并且如果 v 是 White，则将其标记为 Grey 并继续探索其邻居。

但是，如果v为灰色，则表示您在堆栈中第二次遇到v并且您已经完成探索。标记它Black并继续循环。

修改后的代码应如下所示：

procedure DFS-iterative(G,v):
    let S be a stack
    S.push(v)
    while S is not empty
        v = S.peek()
        if v is not labeled as Grey:
            label v as Grey
            for all edges from v to w in G.adjacentEdges(v) do
                if w is labeled White do
                    S.push(w)
                elif w is labeled Grey do
                    return False    # Cycle detected
                                    # if w is black, it's already explored so ignore
        elif v is labeled as Grey:
            S.pop()                 # Remove the stack element as it has been explored
            label v as Black

如果您使用 visited 列表来标记所有访问过的节点和另一个 recStack 即跟踪当前正在探索的节点的列表，那么您可以做的是，而不是从堆栈中弹出元素，只需执行 stack.peek()。如果未访问该元素（这意味着您是第一次在堆栈中遇到该元素），只需在 visited 和 recStack 中将其标记为 True 并探索其子项。

但是，如果已经访问了 peek() 值，则意味着您正在结束对该节点的探索，因此只需将其弹出并再次使其 recStack 为 False。

Answer 4

我已经解决了这个问题作为这个 Leetcode 问题的解决方案 - https://leetcode.com/problems/course-schedule/

我已经在 Java 中实现了它 - 使用使用颜色的递归 DFS，使用访问数组的递归 DFS，使用 indegree 的迭代 DFS 和 BFS 并计算拓扑排序。

class Solution {
    //prereq is the edges and numCourses is number of vertices
    public boolean canFinish(int numCourses, int[][] prereq) {

        //0 -> White, -1 -> Gray, 1 -> Black
        int [] colors = new int[numCourses];
        boolean [] v = new boolean[numCourses];
        int [] inDegree = new int[numCourses];
        Map<Integer, List<Integer>> alMap = new HashMap<>();
        
        for(int i = 0; i < prereq.length; i++){
            int s = prereq[i][0];
            int d = prereq[i][1];
            alMap.putIfAbsent(s, new ArrayList<>());
            alMap.get(s).add(d);
            inDegree[d]++;
        }
        // if(hasCycleBFS(alMap, numCourses, inDegree)){
        //     return false;
        // }
        for(int i = 0; i < numCourses; i++){
            if(hasCycleDFS1(i, alMap, colors)){
            // if(hasCycleDFS2(i, alMap, v)){
            //if(hasCycleDFSIterative(i, alMap, colors)){
                return false;
            }
       }
        return true;
    }
    //12.48
    boolean hasCycleBFS(Map<Integer, List<Integer>> alMap, int numCourses, int [] inDegree){
        //short [] v = new short[numCourses];
        Deque<Integer> q = new ArrayDeque<>();
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] == 0){
                q.offer(i);
            }
        }
        List<Integer> tSortList = new ArrayList<>();
        while(!q.isEmpty()){
            int cur = q.poll();
            tSortList.add(cur);
            //System.out.println("cur = " + cur);
            
            if(alMap.containsKey(cur)){
                for(Integer d: alMap.get(cur)){
                    //System.out.println("d = " + d);
                    // if(v[d] == true){
                    //     return true;
                    // }
                    inDegree[d]--;
                    if(inDegree[d] == 0){
                        q.offer(d);
                    }
                }
            }
        }
       
        return tSortList.size() == numCourses?  false:  true;
    }
    // inspired from - https://leetcode.com/problems/course-schedule/discuss/58730/Explained-Java-12ms-Iterative-DFS-solution-based-on-DFS-algorithm-in-CLRS
    //0 -> White, -1 -> Gray, 1 -> Black
    boolean hasCycleDFSIterative(int s, Map<Integer, List<Integer>> alMap, int [] colors){
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(s);
        while(!stack.isEmpty()){
            int cur = stack.peek();
            if(colors[cur] == 0){
                colors[cur] = -1;
                if(alMap.containsKey(cur)){
                    for(Integer d: alMap.get(cur)){
                        if(colors[d] == -1){
                            return true;
                        }
                        if(colors[d] == 0){
                            stack.push(d);
                        }
                    }
                }
            }else if (colors[cur] == -1 || colors[cur] == 1){
                    colors[cur] = 1;
                    stack.pop();
            }
        }

        return false;
    }
    
    boolean hasCycleDFS1(int s, Map<Integer, List<Integer>> alMap, int [] colors){
        // if(v[s] == true){
        //     return true;
        // }
        colors[s] = -1;
        if(alMap.containsKey(s)){
            for(Integer d: alMap.get(s)){
                //grey vertex
                if(colors[d] == -1){
                    return true;
                }
                if(colors[d] == 0 && hasCycleDFS1(d, alMap, colors)){
                    return true;
                }
            }
        }
        colors[s] = 1;
        return false;
    }
    
    // not efficient because we process black vertices again 
    boolean hasCycleDFS2(int s, Map<Integer, List<Integer>> alMap, boolean [] v){
        // if(v[s] == true){
        //     return true;
        // }
        v[s] = true;
        if(alMap.containsKey(s)){
            for(Integer d: alMap.get(s)){
                if(v[d] == true || hasCycleDFS2(d, alMap, v)){
                    return true;
 
                }
            }
        }
        v[s] = false;
        return false;
    }
    
}

Answer 5

Java版本：

public class CycleDetection {
    private List<ArrayList<Integer>> adjList = new ArrayList<>();
    private boolean[] visited;

    public static void main(String[] args) {
        CycleDetection graph = new CycleDetection();
        graph.initGraph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        //graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        //graph.addEdge(3, 3);
        System.out.println(graph.isCyclic());
    }

    private boolean isCyclic() {
        Stack<Integer> stack = new Stack<>();
        //DFS
        boolean[] recStack = new boolean[this.adjList.size()];
        stack.add(0);//push root node
        while (!stack.empty()) {
            int node = stack.pop();
            /*if (recStack[node]) {
                return true;
            }*/
            visited[node] = true;
            recStack[node] = true;
            List<Integer> neighbours = this.adjList.get(node);
            ListIterator<Integer> adjItr = neighbours.listIterator();
            while (adjItr.hasNext()) {
                int currentNode = adjItr.next();
                if (!visited[currentNode]) {
                    visited[currentNode] = true;
                    stack.push(currentNode);
                } else {
                    if (recStack[currentNode]) {
                        return true;
                    }
                }
            }
            if (neighbours == null || neighbours.isEmpty())
                recStack[node] = false;

        }

        return false;
    }

    private void initGraph(int nodes) {
        IntStream.range(0, nodes).forEach(i -> adjList.add(new ArrayList<>()));
        visited = new boolean[nodes];
    }

    private void addEdge(int u, int v) {
        this.adjList.get(u).add(v);
    }
}

如何使用 DFS 的迭代版本检测有向图中的循环？

How to detect cycles in a directed graph using the iterative version of DFS?

algorithm

depth-first-search

graph-algorithm