|
|
本文主要针对如何判断有向图/无向图中是否存在环的问题进行简单的论述。
一 无向图
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中一个顶点的未被访问的邻接点，相当于生成树中的该顶点的子孙节点) |
|
发表于 2020-11-28 11:08:13
收藏
楼主
