华师一附中OI组

标题: 无向图的判环问题 [打印本页]

---

作者: admin    时间: 2020-11-28 11:08
标题: 无向图的判环问题
本文主要针对如何判断有向图/无向图中是否存在环的问题进行简单的论述。

一 无向图

1.利用DFS进行判断

利用DFS判断有向图是否存在环，是最为常用的一种方法，虽然这种方法很常用，但可参考的代码的实现比较少，下面对这种方法及其实现进行详细的阐述。

首先，利用DFS判断无向图中是否换的原理是：若在深度优先搜索的过程中遇到回边(即指向已经访问过的顶点的边)，则必定存在环。

所以说，是否存在环的关键在于是否存在满足条件的“回边”，那么如何判断回边呢？

(1)首先，对图中的所有顶点定义三种状态：顶点未被访问过、顶点刚开始被访问、顶点被访问过并且其所有邻接点也被访问过。这三种状态，在visited数组中分别用0、1、2来表示。那么，存在环的情况可以定义为：在遍历过程中，发现某个顶点的一条边指向状态1的顶点，此时就存在环。状态2可以理解为其生成树上的所有的子孙节点都已经访问完。

(2)此外，我们要定义一个father数组，用以存储在DFS过程中顶点的父顶点(或者说是生成树上的父节点)。其主要作用是为了区分邻接点中环中的顶点和遍历过程中的父节点 (单纯的用visited数组无法区分)。

整个过程的实现代码如下：



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
#define MAX_NUM 100
#define INF 0x7fffffff
/*DFS判断无向图中是否有环*/
class Graph
{
    public:
    int vertexNum;//顶点个数
    int arcNum;//弧的个数
    int vertex[MAX_NUM];//顶点表
    int arc[MAX_NUM][MAX_NUM];//弧信息表
};
int visited[MAX_NUM];//顶点访问表
int father[MAX_NUM];//父节点表
void DFS(int v,Graph G)
{
    visited[v] = 1;
    for(int i = 0 ; i < G.vertexNum; i++)
    {
        if(i != v && G.arc[v][i] != INF)//邻接矩阵中节点v的邻接点
        {
            if(visited[i] == 1 && father[v] != i)//vi不是父节点，而且还访问过(而且为状态1，说明不是回溯过来的顶点)，说明存在环(判断i不是v的父节点)
            {
                cout<<"图存在环";
                int temp = v;
                while(temp != i)
                {
                    cout<<temp<<"<-";//输出环
                    temp = father[temp];
                }
                cout<<temp<<endl;
            }
            else
                if(visited[i] == 0)
                {
                    father[i] = v;//更新father数组
                    DFS(i,G);
                }

        }
    }
    visited[v] = 2;//遍历完所有的邻接点才变为状态2
}
void DFSTraverse(Graph G)
{
    memset(visited,0,sizeof(visited));
    memset(father,-1,sizeof(father));
    for(int i = 0 ; i < G.vertexNum; i++)
        if(!visited[i])
            DFS(i,G);
}


　　



由此可见，visited数组相对于一般的情况，增加了个状态2，主要是为了防止在回溯过程中进行误判。所以才能仅用father数组和状态1判断存在环。

状态2可以理解为其生成树上的所有的子孙节点都已经访问完。

由于使用的是邻接矩阵来存储，所以该算法的时间复杂度为O(n^2),空间复杂度为O(n)。

2.其他方法本文不再详述。

二 有向图

1.拓扑排序

关于拓扑排序，资料很多，本文不再详述其原理，只给出其实现代码，代码如下：



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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<unordered_map>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<sstream>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define MAX_NUM 100
#define INF 0x7fffffff
/*拓扑排序*/
int indegree[MAX_NUM];//用以表示每个顶点的入度
bool visited[MAX_NUM];//用以表示该顶点是否入栈
class Graph
{
public:
    int vertexNum;//顶点个数
    int arcNum;//弧的个数
    int vertex[MAX_NUM];//顶点表
    int arc[MAX_NUM][MAX_NUM]= {{0,1,1},{INF,0,1},{INF,INF,0}}; //弧信息表
};
void Initindegree(Graph G)//初始化入度数组
{
    memset(indegree,0,sizeof(indegree));
    for(int i = 0; i < G.vertexNum; i++)
        for(int j = 0; j < G.vertexNum; j++)
        {
            if(i != j && G.arc[i][j] != INF)
                indegree[j]++;//注意此处增加的是顶点vj的入度
        }
    memset(visited,0,sizeof(visited));
}
bool TuoPu(Graph G)
{
    stack<int> s;
    int cnt = 0;//用于记录拓扑序列中节点的个数
    for(int i = 0 ; i < G.vertexNum; i++)
        if(indegree[i] == 0)
        {
            s.push(i);
            visited[i] = true;//修改入栈顶点的入栈标记数组

        }
    while(!s.empty())
    {
        int v = s.top();
        cnt++;//顶点出栈得到时候，计数器加1
        s.pop();

        for(int i = 0; i < G.vertexNum; i++)
        {
            if(v != i && G.arc[v][i] != INF && visited[i] == false)//将所有顶点v的未入栈的邻接点的入度都减去1
            {
                indegree[i]--;
                if(indegree[i] == 0)//如果减1后入度为0了，此时需要将该邻接点入栈，且修改入栈标记数组
                {
                    visited[i] = true;
                    s.push(i);
                }
            }


        }
    }
    return cnt == G.vertexNum ? true : false;
}
int main()
{
    Graph G;
    G.vertexNum = 3;
    Initindegree(G);
    cout<<TuoPu(G)<<endl;

}


　　



2.利用改进的DFS

对于有向图的话，如果直接应用一般的DFS的话，会出现误判的情况，一个典型的例子是：A->B,A->C->B,我们用DFS来处理这个图，我们会得出它有环，但实际上并没有。然而，本文中所说的无向图的DFS判断算法完全可以直接应用到有向图中来，即上述代码可以直接应用到有向图中来。所以说上述的DFS算法(或称为为改进的DFS算法)既适用于无向图，也适用于有向图。其对应的原理适用于这两种图，即只要我们在遍历过程中，只要发现一个顶点不是当前节点的父节点，同时他还被访问过了(状态为1)，那么就可以认为此处存在环。(通常在DFS中一个顶点的未被访问的邻接点，相当于生成树中的该顶点的子孙节点)

---

作者: admin    时间: 2020-11-28 11:09
无向图
方法1（数学方法）： 图的顶点数为n，边数为m，若n>=m+1，则无环;否则有环。
方法2：使用并查集进行判断。
方法3：DFS。使用visited数组辅助判断是否访问过。

有向图
方法1：拓扑排序。每次取出入度为0为节点，并删除对应的边，如果最后还有节点则有环。
方法2：DFS。使用一个color数组表示节点类型，color=0表示该节点未被访问，color=1表示该节点正在当前访问的路径中或该节点存在于环路中，color=2表示该节点是安全不存在于环中的。

作者：RiceCake1122
链接：https://www.jianshu.com/p/6e1deeb0bdd5
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2