图论算法＜三＞：判断有向图中是否有存在循环 ，以及环的个数和各个环中的元素

1、目的

  判断有向图中是否有存在循环 ，以及环的个数和各个环中的元素。
原理：利用DFS求有向图中所有点任意两点之间的所有路径，然后判断环路径并存起来。其中辅助数组visited[]用来记录路径中是否有重复点。

2、示例效果

2.1 原始数据

路线起终点整理如下：

// 共计12个顶点，19条边。 （起点，终点，1）最后的1代表起点终点是连通的。
起点，终点，1：2 4 1
起点，终点，1：9 10 1
起点，终点，1：8 11 1
起点，终点，1：4 12 1
起点，终点，1：11 12 1
起点，终点，1：1 2 1
起点，终点，1：3 2 1
起点，终点，1：1 3 1
起点，终点，1：3 4 1
起点，终点，1：3 6 1
起点，终点，1：1 5 1
起点，终点，1：6 5 1
起点，终点，1：6 7 1
起点，终点，1：6 9 1
起点，终点，1：7 9 1
起点，终点，1：9 10 1
起点，终点，1：5 8 1
起点，终点，1：8 7 1
起点，终点，1：10 11 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

为方便测试：将分支的起终点互换改为：e13:7-6; e3:11-8.

2.2 程序计算效果

3、算法源码

// CheckGraphCircle.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include 
#include 
using namespace std;
const int MAX_Vertex_Num = 500;
template<class VexType, class ArcType>
class MGraph
{
public:
	//创建图
	void CreateGraph();//创建图

	//返回顶点v所在顶点向量中的位置（下标）
	int LocateVex(VexType v);

	//检查图中有无环
	bool CheckCircle(int& nCount,std::vector<vector<int>>& vecCircle);

private:
	VexType m_vexs[MAX_Vertex_Num];//顶点向量
	ArcType m_arcs[MAX_Vertex_Num][MAX_Vertex_Num]; //这里把邻接矩阵类型用模板表示，主要是为了处理有权值的情况，比如：权值可以为小数，也可以为整数
	int m_vexNum;//顶点数
	int m_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, std::vector<vector<int>>& vecCircle);
};

template<class VexType, class ArcType>
void MGraph<VexType, ArcType>::CreateGraph()
{
	//VexType first;
	//VexType Secend;
	//cout << "请输入顶点数:";
	//cin >> vexnum;
	//cout << "请输入边数:";
	//cin >> arcnum;

	m_vexNum = 12;
	cout << "顶点数: 12" << endl;
	m_arcNum = 19;
	cout << "边数: 19" << endl;

	//cout << "请输入各个顶点值：";
	for (int i = 1; i <= m_vexNum; i++)
	{
		//cin >> vexs[i];
		m_vexs[i] = i;
	}

	//初始化邻接矩阵
	for (int i = 0; i < m_arcNum; i++)
	{
		for (int j = 0; j < m_arcNum; j++)
		{
			m_arcs[i][j] = 0;
		}
	}

	// 为边赋值
	m_arcs[2][4] = 1;

	m_arcs[9][10] = 1;

	m_arcs[11][8] = 1;

	m_arcs[4][12] = 1;

	m_arcs[11][12] = 1;

	m_arcs[1][2] = 1;

	m_arcs[3][2] = 1;

	m_arcs[1][3] = 1;

	m_arcs[3][4] = 1;

	m_arcs[3][6] = 1;

	m_arcs[1][5] = 1;

	m_arcs[6][5] = 1;

	m_arcs[7][6] = 1;

	m_arcs[6][9] = 1;

	m_arcs[7][9] = 1;

	m_arcs[9][10] = 1;

	m_arcs[5][8] = 1;

	m_arcs[8][7] = 1;

	m_arcs[10][11] = 1;

	//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 < m_vexNum; i++)
	{
		if (m_vexs[i] == v)
		{
			return i;
		}
	}
	return -1;
}

/*
检查图中是不是有回向边
思想：
如果有回向边，则无环，反之有环
*/
template<class VexType, class ArcType>
bool MGraph<VexType, ArcType>::CheckCircle(int& nCount, std::vector<vector<int>>& vecCircle)
{
	nCount = 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 < m_vexNum; i++)
	{
		if (!visited[i])
		{
			DFS(i, visited, stack, top, inStack, nCount, vecCircle);
		}
	}

	return (nCount > 0) ? true : false;
}

bool CompareVector(vector<int> vec1, vector<int> vec2)
{
	if (vec1.size() != vec2.size())
	{
		return false;
	}

	if(vec1.size() == 0)
	{
		return true;
	}

	int nFirstValue = vec1[0];
	int nIndex = -1;
	for (int i = 0; i < vec2.size(); ++i)
	{
		if (vec2[i] == nFirstValue)
		{
			nIndex = i;
			break;
		}
	}

	int nCounter = 0;
	vector<int> vecMid;
	for (int i = 0; i < vec2.size(); ++i)
	{
		if (nIndex > vec2.size() - 1)
		{
			nIndex = 0;
		}
		vecMid.push_back(vec2[nIndex]);
		nIndex++;
	}

	for (int i = 0; i < vec1.size(); ++i)
	{
		if (vec1[i] != vecMid[i])
		{
			return false;
		}
	}

	return true;
}

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& nCount, std::vector<vector<int>>& vecCircle)
{
	visited[x] = true;
	stack[++top] = x;
	inStack[x] = true;
	for (int i = 0; i < m_vexNum; i++)
	{
		if (m_arcs[x][i] != 0)//有边
		{
			if (!inStack[i])
			{
				DFS(i, visited, stack, top, inStack, nCount, vecCircle);
			}
			else //条件成立，表示下标为x的顶点到 下标为i的顶点有环
			{
				nCount++;
				//cout << "第"<< nCount << "环为:";
				//从i到x是一个环，top的位置是x，下标为i的顶点在栈中的位置要寻找一下
				//寻找起始顶点下标在栈中的位置
				int t = 0;
				for (t = top; stack[t] != i; t--);
				//输出环中顶点
				vector<int> vecNode;
				for (int j = t; j <= top; j++)
				{
					//cout << (int)m_vexs[stack[j]];
					vecNode.push_back((int)m_vexs[stack[j]]);
				}
				//cout << endl;

				bool bHas = false;
				for (int i = 0; i < vecCircle.size(); i++)
				{
					vector<int> vecTemp = vecCircle[i];
					if (CompareVector(vecTemp, vecNode))
					{
						bHas = true;
						break;
					}
				}

				if (!bHas)
				{
					vecCircle.push_back(vecNode);
				}
			}
		}
	}
	//处理完结点后，退栈
	top--;
	inStack[x] = false;
}

int main()
{
	MGraph<char, int> myGraph;
	myGraph.CreateGraph();

	int nCount = 0;
	std::vector<vector<int>> vecCircle;
	if (myGraph.CheckCircle(nCount, vecCircle))
	{
		cout << "当前图中存在局部循环个数：" << vecCircle.size() << endl;
	}
	else
	{
		cout << "当前图中不存在局部循环！" << endl;
	}

	for (int i = 0; i < vecCircle.size(); i++)
	{
		cout << "第" << i << "个环为:";

		vector<int> vecTemp = vecCircle[i];
		for (int j = 0; j < vecTemp.size(); j++)
		{
			cout << vecTemp[j] << " ";
		}

		cout << endl;
	}
	
	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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284