判断有向图是否有环 、环的个数以及环中元素

判断有向图是否有环有三种方法：拓扑排序、深度遍历+回溯、深度遍历 + 判断后退边

这里使用 拓扑排序 和 深度遍历 + 回溯判断是不是环。使用 深度遍历 + 判断后退边找出环个数 以及环中元素

1、拓扑排序

思想：找入度为0的顶点，输出顶点，删除出边。循环到无顶点输出。

若：输出所有顶点，则课拓扑排序，无环；反之，则不能拓扑排序，有环

使用：可以使用拓扑排序为有向无环图每一个结点进行编号，拓扑排序输出的顺序可以为编号顺序

源代码：

[cpp] view plain
copy

#include <iostream>
using namespace std;
const int MAX_Vertex_Num = 20;
template<class VexType,class ArcType>
class MGraph
{
public:
void CreateGraph();//创建图
int LocateVex(VexType v);//返回顶点v所在顶点向量中的位置（下标）
void CheckCircle();
private:
VexType vexs[MAX_Vertex_Num];//顶点向量
ArcType arcs[MAX_Vertex_Num][MAX_Vertex_Num]; //这里把邻接矩阵类型用模板表示，主要是为了处理有权值的情况，比如：权值可以为小数（代价），也可以为整数
int vexnum;//顶点数
int arcnum;//边数
private:
bool TopSort();
};

template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::CreateGraph()
{
VexType first;
VexType Secend;
cout<<"请输入顶点数:";
cin>>vexnum;
cout<<"请输入边数:";
cin>>arcnum;
cout<<"请输入各个顶点值：";
for (int i=0;i<vexnum;i++)
{
cin>>vexs[i];
}
//初始化邻接矩阵
for (int i=0;i<arcnum;i++)
{
for (int j=0;j<arcnum;j++)
{
arcs[i][j]=0;
}
}
cout<<"请输入边的信息:"<<endl;
for (int i=0;i<arcnum;i++)
{
cin>>first>>Secend;
//如果边有权值的话，则还应该输入权值
int x = LocateVex(first);
int y = LocateVex(Secend);
arcs[x][y]=1;//如果是有权的话，这里应该是arc[x][y]=权值
}
}
/*
参数：v：表示顶点向量中一个值
函数返回值：函数返回v在顶点向量中的下标
*/
template<class VexType,class ArcType>
int MGraph<VexType,ArcType>::LocateVex(VexType v)
{
for (int i=0;i<vexnum;i++)
{
if (vexs[i]==v)
{
return i;
}
}
return -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

有向图可以拓扑排序的条件是：图中没有环。
具体方法：
⑴ 从图中选择一个入度为0的点加入拓扑序列。
⑵ 从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。

*/
template<class VexType,class ArcType>
bool MGraph<VexType,ArcType>::TopSort()
{
int count = 0;//拓扑排序输出顶点的个数
int top = -1;
int stack[MAX_Vertex_Num];
int indegree[MAX_Vertex_Num]={0};
//求各个顶点的入度--邻接矩阵要查询该元素的列（记录入度情况）--
//如果是邻接表，就是麻烦在这里，查询结点入度很不方便
for (int i=0;i<vexnum;i++)
{
int num=0;
for (int j=0;j<vexnum;j++)
{
if (arcs[j][i]!=0)
{
num++;
}
}
indegree[i]=num;
}
//把入度为0的顶点入栈
for (int i=0;i<vexnum;i++)
{
if (!indegree[i])
{
stack[++top]=i;//顶点的下标
}
}
//处理入度为0的结点：把入度为0的结点出栈，删除与之有关的边
while (top>-1)
{
int x = stack[top--];
cout<<vexs[x];
count++;
//把与下标为x的顶点有关的边都去掉（出边）,并改变对应结点的入度
for (int i=0;i<vexnum;i++)
{
if (arcs[x][i]!=0)
{
arcs[x][i]=0;//删除到下标为i的顶点的边，这时此顶点的入度减一
indegree[i]--;
if (!indegree[i])//顶点的入度为0，则入栈
{
stack[++top]=i;
}
}
}
}
cout<<endl;
if (count == vexnum) //能拓扑排序
{
return true;
}
return false;
}
/*
检查图中是不是有环
思想：
能进行拓扑排序，则无环，反之有环
*/
template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::CheckCircle()
{
if (TopSort())
{
cout<<"无环！"<<endl;
}
else
{
cout<<"有环！"<<endl;
}
}

int main()
{
MGraph<char,int> G;
G.CreateGraph();
G.CheckCircle();
system("pause");
return 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
79
80
81
82
83

测试：

有向图：

结果：

2、深度遍历 + 回溯

思想：用回溯法,遍历时，如果遇到了之前访问过的结点，则图中存在环。

代码：

[cpp] view plain
copy

#include <iostream>
using namespace std;
const int MAX_Vertex_Num = 20;
template<class VexType,class ArcType>
class MGraph
{
public:
void CreateGraph();//创建图
int LocateVex(VexType v);//返回顶点v所在顶点向量中的位置（下标）
bool CheckCircle();//检查图中有无环
private:
VexType vexs[MAX_Vertex_Num];//顶点向量
ArcType arcs[MAX_Vertex_Num][MAX_Vertex_Num]; //这里把邻接矩阵类型用模板表示，主要是为了处理有权值的情况，比如：权值可以为小数（代价），也可以为整数
int vexnum;//顶点数
int arcnum;//边数
private:
void CheckCircle(int u,bool& isExist,bool visited[MAX_Vertex_Num],bool Isvisited[MAX_Vertex_Num]);
};

template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::CreateGraph()
{
VexType first;
VexType Secend;
cout<<"请输入顶点数:";
cin>>vexnum;
cout<<"请输入边数:";
cin>>arcnum;
cout<<"请输入各个顶点值：";
for (int i=0;i<vexnum;i++)
{
cin>>vexs[i];
}
//初始化邻接矩阵
for (int i=0;i<arcnum;i++)
{
for (int j=0;j<arcnum;j++)
{
arcs[i][j]=0;
}
}
cout<<"请输入边的信息:"<<endl;
for (int i=0;i<arcnum;i++)
{
cin>>first>>Secend;
//如果边有权值的话，则还应该输入权值
int x = LocateVex(first);
int y = LocateVex(Secend);
arcs[x][y]=1;//如果是有权的话，这里应该是arc[x][y]=权值
}
}
/*
参数：v：表示顶点向量中一个值
函数返回值：函数返回v在顶点向量中的下标
*/
template<class VexType,class ArcType>
int MGraph<VexType,ArcType>::LocateVex(VexType v)
{
for (int i=0;i<vexnum;i++)
{
if (vexs[i]==v)
{
return i;
}
}
return -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

思想：用回溯法,遍历时，如果遇到了之前访问过的结点，则图中存在环。
引入visited数组的原因：
1）在一次深度遍历时，检测路径上是否结点是否已经被检测到，如果被重复检测，则表示有环。
2）注意，在深度递归返回时，总是要把visited置为false。
引入Isvisited数组的原因：
1）用于记录目前为止深度遍历过程中遇到的顶点。
2）因为，我们不一定以所有结点为起始点都进行一次深度遍历。
3）举例，在结点A为起点，进行深度遍历时，遇到了结点B，此时Isvisited在A和B两个位置都为true。
那么没遇到环，那么我们就不用再以B为起始点继续进行一次深度遍历了，
因为A为起点的深度遍历已经验证不会有环了。

*/
template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::CheckCircle(int u,bool& isExist,bool visited[MAX_Vertex_Num],bool Isvisited[MAX_Vertex_Num])
{
visited[u]=true;
Isvisited[u]=true;
for (int j=0;j<vexnum;j++)
{
if (arcs[u][j]==1)
{
if (visited[j]==false)
{
CheckCircle(j,isExist,visited,Isvisited);
}
else
{
isExist = true;
}
}
}
visited[u]=false;//回溯，如果不写就变成一半的深度遍历，不能进行判断是否有边存在
}

template<class VexType,class ArcType>
bool MGraph<VexType,ArcType>::CheckCircle()
{
bool isExist = false;
bool Isvisited[MAX_Vertex_Num]={false};
bool visited[MAX_Vertex_Num]={false};
for (int i=0;i<vexnum;i++)
{
if (Isvisited[i]==false)
{
CheckCircle(i,isExist,visited,Isvisited);
if (isExist)
{
return true;
}
}
}
return isExist;
}

int main()
{
MGraph<char,int> G;
G.CreateGraph();
if (G.CheckCircle())
{
cout<<"图存在环！"<<endl;
}
else
{
cout<<"图不存在环！"<<endl;
}
system("pause");
return 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

结果测试：

图：

结果：

3、深度遍历 + 判断后退边

思想：用DFS（深度优先遍历）,判断是否有后退边，若有，则存在环

具体来说，在遍历顶点的每一条边时，判断一下这个边的顶点是不是在栈中，如果在栈中，说明之前已经访问过了，这里再次访问，说明有环存在

判断后退边时，借助一个栈和一个数组

栈：即可以用来输出环

数组：inStack判断是否在栈中

源代码：

[cpp] view plain
copy

#include <iostream>
using namespace std;
const int MAX_Vertex_Num = 20;
template<class VexType,class ArcType>
class MGraph
{
public:
void CreateGraph();//创建图
int LocateVex(VexType v);//返回顶点v所在顶点向量中的位置（下标）
void CheckCircle();
private:
VexType vexs[MAX_Vertex_Num];//顶点向量
ArcType arcs[MAX_Vertex_Num][MAX_Vertex_Num]; //这里把邻接矩阵类型用模板表示，主要是为了处理有权值的情况，比如：权值可以为小数（代价），也可以为整数
int vexnum;//顶点数
int arcnum;//边数
private:
void DFS(int x,bool visited[MAX_Vertex_Num],int stack[MAX_Vertex_Num],int& top,bool inStack[MAX_Vertex_Num],int& count);

};

template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::CreateGraph()
{
VexType first;
VexType Secend;
cout<<"请输入顶点数:";
cin>>vexnum;
cout<<"请输入边数:";
cin>>arcnum;
cout<<"请输入各个顶点值：";
for (int i=0;i<vexnum;i++)
{
cin>>vexs[i];
}
//初始化邻接矩阵
for (int i=0;i<arcnum;i++)
{
for (int j=0;j<arcnum;j++)
{
arcs[i][j]=0;
}
}
cout<<"请输入边的信息:"<<endl;
for (int i=0;i<arcnum;i++)
{
cin>>first>>Secend;
//如果边有权值的话，则还应该输入权值
int x = LocateVex(first);
int y = LocateVex(Secend);
arcs[x][y]=1;//如果是有权的话，这里应该是arc[x][y]=权值
}
}
/*
参数：v：表示顶点向量中一个值
函数返回值：函数返回v在顶点向量中的下标
*/
template<class VexType,class ArcType>
int MGraph<VexType,ArcType>::LocateVex(VexType v)
{
for (int i=0;i<vexnum;i++)
{
if (vexs[i]==v)
{
return i;
}
}
return -1;
}

/*
检查图中是不是有回向边
思想：
如果有回向边，则无环，反之有环
*/
template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::CheckCircle()
{
int count=0;//环的个数
int top=-1;
int stack[MAX_Vertex_Num];
bool inStack[MAX_Vertex_Num]={false};
bool visited[MAX_Vertex_Num]={false};
for (int i=0;i<vexnum;i++)
{
if (!visited[i])
{
DFS(i,visited,stack,top,inStack,count);
}
}
}

template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::DFS(int x,bool visited[MAX_Vertex_Num],int stack[MAX_Vertex_Num],int& top,bool inStack[MAX_Vertex_Num],int& count)
{
visited[x]=true;
stack[++top]=x;
inStack[x]=true;
for (int i=0;i<vexnum;i++)
{
if (arcs[x][i]!=0)//有边
{
if (!inStack[i])
{
DFS(i,visited,stack,top,inStack,count);
}
else //条件成立，表示下标为x的顶点到 下标为i的顶点有环
{
count++;
cout<<"第"<<count<<"环为:";
//从i到x是一个环，top的位置是x，下标为i的顶点在栈中的位置要寻找一下
//寻找起始顶点下标在栈中的位置
int t=0;
for (t=top;stack[t]!=i;t--);
//输出环中顶点
for (int j=t;j<=top;j++)
{
cout<<vexs[stack[j]];
}
cout<<endl;
}
}
}
//处理完结点后，退栈
top--;
inStack[x]=false;
}
int main()
{
MGraph<char,int> G;
G.CreateGraph();
G.CheckCircle();
system("pause");
return 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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

来源：http://blog.csdn.net/insistgogo/article/details/6978718