图——判断有向图中是否有环_有向图判环

1. 判断有向图中是否有环

给定有向图，检查该图是否包含循环。如果给定图包含至少一个循环，则函数应返回true，否则返回false。

1.1. 方法一：DFS

1.1.1. 思路

对一个图进行DFS， 则DFS的路径可以生成一个棵树。

对于DFS树上的结点，如果存在指向祖先的边或指向自己边，则图存在回路。（这种边叫做后向边）

---

下面通过图来描述一下：

有向图，如下。

其DFS树为：

但是当你DFS到3结点时 会存在后向边，如图：

所以这个有向图存在环路

1.1.2. 实现过程

首先需要两个辅助数组。

vis数组:用来标记节点是否已被访问。

recStack数组(或集合)：一个用来标记递归栈中的节点（或者说递归过程中的节点）。

1. 一个递归函数isCyclicUtil，标记当前节点v已被访问，并且标记它在递归栈中
2. 循环遍历与v相连的节点
3. 如果该节点未被访问，则递归调用该节点的isCyclicUtil，如果返回true，则当前就返回true
4. 如果该节点已被访问，并且在递归栈中，则返回true
5. 其他情况，返回false
6. 创建一个isCyclic函数，循环调用每个节点的isCycticUtil。如果任意一个返回true，则该函数isCyclic返回true。否则返回false。

其实isCyclicUtil就是DFS函数稍加修改。

1.1.3. 实现代码

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
vector<vector<int> > g(N);
bool isCyclicUtil(int v, bool vis[],bool recStack[])
{
    if (!vis[v])
    {
        vis[v] = recStack[v] = true;
        for(int i = 0;i < g[v].size();++ i)
        {
            if (!vis[g[v][i]] && isCyclicUtil(g[v][i], vis, recStack))
                return true;
            else if (recStack[g[v][i]])
                return true;
        }
    }
    recStack[v] = false;
    return false;
}

bool isCyclic(int n)
{
    bool vis[n],recStack[n];
    for(int i = 0;i < n;++ i)
        vis[i] = recStack[i] = false;
    for(int i = 0;i < n;++ i)
    {
        if (isCyclicUtil(i, vis, recStack))
            return true;
    }
    return false;
}

int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < m;++ i)
    {
        int from, to;
        cin >> from >> to;
        g[from].push_back(to);
    }
    cout << (isCyclic(n) ? "yes" : "no");
    return 0;
}
/*
input
output
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

1.1.3. 复杂度分析

时间复杂度：$O（V+E）$。

• 该方法的时间复杂度与DFS遍历的时间复杂度相同，为$O（V+E）$。

空间复杂度：$O（V）$。

• 为了存储已访问结点和递归栈，需要$O（V）$空间。

参考

• https://www.cnblogs.com/-yyyan/p/13383496.html
• https://www.geeksforgeeks.org/detect-cycle-in-a-graph/