detect cycle in DFS

突然发现自己并不理解 为什么需要3个状态 而不是2个状态 visited 0/1 去判断directed graph有没有cycle 呀 ? 这里我肯定漏了什么，
有没有什么反例？  谢谢

```
    bool findCycle(int current,const vector<vector<int>>& graph, vector<int>&visited){
        if(visited[current]){
            return false;
        }
        visited[current]=true;
        for(const int& next_node: graph[current]){
            if(!findCycle(next_node,graph,visited)){
                return false;
            }
        }
        visited[current]=false;
        return true;

    }
```

简单来说，3个状态分别代表
1. 仍在调用栈上的节点
2. 未访问的节点
3. 已访问且退出调用栈的节点

当且仅当遇到1类节点时，图是cyclic的。
往细了说不完，建议LZ参考CLRS的22.3。DFS往深了考可以很难，所以我觉得还是有必要系统学习一下的。
p.s. LZ的代码举个反例，想象一个菱形，从左顶点分别经由上下顶点到右顶点（相当于2个stream），这种情况是acyclic的，但LZ的代码会判断成cyclic。

您好楼主，我看其他答主的答案都很完善了，想提供另外一种思路。
其实cycle detection 可以用BFS-based topological sort来实现。

对图跑一遍topological sort然后看遍历的节点数量是否等于图的节点数量。

https://www.geeksforgeeks.org/de ... ed-graph-using-bfs/

maristie 发表于 2021-6-29 18:46
简单来说，3个状态分别代表
1. 仍在调用栈上的节点
2. 未访问的节点

感谢回复，我演练了一下你说的菱形的栗子感觉用这个代码是可以判断的呀，当扫到最下面的节点D时，已经到头，没有孩子节点可以遍历了， 所以会恢复它的visited[i]->false， 然后从头再继续遍历，希望指正问题，谢谢。 btw 上面的代码true or false 好像写反了
      
A -> B
|       |
V      V
C - >D

```
    bool findCycle(int current,const vector<vector<int>>& graph, vector<int>&visited){
        if(visited[current]){
            return false;
        }
        visited[current]=true;
        for(const int& next_node: graph[current]){
            if(findCycle(next_node,graph,visited)){
                return true;
            }
        }
        visited[current]=false;
        return false;

    }
```

没法给楼主加米.

"抱歉，您不能对匿名帖评分"

可以想象有4个node 0，1，2，3
directed edge:

(0,1)
(0,2)
(2,1)
(2,3)

从0开始dfs，1没有后续child，mark 1 visited
然后进入2，2会走到1，发现1visited，然后就会误以为cycle

martingalemsy 发表于 2021-6-30 02:17
感谢回复，我演练了一下你说的菱形的栗子感觉用这个代码是可以判断的呀，当扫到最下面的节点D时，已经到 ...

这段代码好像work，但肯定效率不高，因为你把访问过的点改为没访问过，下次就还要继续访问，你举的例子里，如果D能连向一个非常大的图里，那么A->B->D访问过后，A->C->D又要再访问一次

2个状态 3个状态都一样，2个状态就是会重复访问已经访问过的点

youziwry 发表于 2021-6-30 03:11
这段代码好像work，但肯定效率不高，因为你把访问过的点改为没访问过，下次就还要继续访问，你举的例子里 ...

了解了，谢谢:D

woshiduga 发表于 2021-6-30 03:54
2个状态 3个状态都一样，2个状态就是会重复访问已经访问过的点

了解了，谢谢:D

dfs的时候把parent node一起传下去，每次loop遇到parent node就skip.
这样2个状态就够了.