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

Question

在递归 DFS 中，我们可以通过将节点着色为

WHITE

、

GRAY

和

BLACK

来检测循环，如此处所述。

如果在 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

您只需不立即弹出堆栈元素即可做到这一点。对于每次迭代，执行

v = stack.peek()

，如果

是

White

，则将其标记为

Grey

并继续探索其邻居。

但是，如果

是灰色的，则表示你在堆栈中第二次遇到了

，并且你已经完成了对它的探索。标记它

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()

。如果该元素未被访问（这意味着您是第一次在堆栈中遇到该元素），只需在

True

和

visited

中将其标记为

recStack

并探索其子元素即可。

但是，如果

peek()

值已被访问，则意味着您将结束对该节点的探索，因此只需将其弹出并再次将其

recStack

设置为 False。

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

在

DFS

中，分支的末端是没有子节点的节点，这些节点是 Black。然后检查这些节点的父节点。如果父母没有

Gray

孩子，那么它就是 Black。同样，如果继续将节点设置为黑色，则所有节点的颜色都将变为黑色。

例如，我想执行下图中的

DFS

。

DFS

从

出发，参观了

u -> v -> y -> x

。

没有子节点，您应该将此节点的颜色更改为Black。

然后根据

返回到访问路径中

discovery time

的父级。所以

的父级是

。

没有具有

Gray

颜色的子节点，因此您应该将此节点的颜色更改为 Black。

Answer 4

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

我已经用Java实现了它 - 使用颜色的递归DFS，使用访问数组的递归DFS，使用入度的迭代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);
    }
}

Answer 6

我想对 Pranav Gor 的答案进行一个小修正。如果我按照给定的方式运行这个算法，它会多次遍历某些边。修复后的版本如下。

from enum import Enum

class Color(Enum):
    White = 0
    Grey  = 1
    Black = 2

class Vertex:
    def __init__(self):
        self.color = Color.White
        self.neighbors = []

N = 5
vs = list(map(lambda _: Vertex(), [None] * N))

ACCESS_COUNT = EDGE_COUNT = 0

for i in range(N):
    for j in range(N - 1, i, -1):
        vs[i].neighbors.append(j)
        EDGE_COUNT += 1

def dfs_iterative(u: int) -> bool:
    global vs, ACCESS_COUNT

    stack = []
    stack.append(u)

    while len(stack) > 0:
        u = stack[len(stack) - 1]

        if vs[u].color == Color.White:
            vs[u].color = Color.Grey
            for v in vs[u].neighbors:
                ACCESS_COUNT += 1
                print(f"{u} -> {v}")

                if vs[v].color == Color.White:
                    stack.append(v)

                elif vs[v].color == Color.Grey:
                    return False

                # == Black -> do nothing

        elif vs[u].color == Color.Grey:
            stack.pop()
            vs[u].color = Color.Black

        elif vs[u].color == Color.Black:
            stack.pop()

    return True

print(dfs_iterative(0))
print(EDGE_COUNT, ACCESS_COUNT)

P.S.：也许写评论更合适，但我不能，因为没有 50 声望。

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

问题描述投票：0回答：6

6个回答

最新问题

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

问题描述 投票：0回答：6

6个回答

最新问题

问题描述投票：0回答：6