概述

判断无向图是否存在环是一个非常基础的操作，然后也对应了比较多的解法，我们用c++来做一些基础的实现。

题目给的条件是顶点个数、边的个数、边的信息。顶点的序号从0到n-1排列。

并查集解法

并查集有两个主要操作：

  • Union操作：将一条边对应的两个顶点放到一个连通集里，集合里的所有顶点都连通
  • Find操作：查询一个顶点所在集合的“老大”，并返回“老大”的编号

并查集原理

几句话解释一下为什么要用并查集，以及怎么用：

  • 首先，并查集的特点是，将所有边的信息收录进一个parent数组，因此，当需要查询两个顶点是否连通的时候，只需要分别对两个顶点编号进行Find操作，然后比较返回值，返回值相同，拥有共同的老大，因此他们是连通的，返回值不同，则不连通。
  • 其次，当我读取边的信息时，读入一对顶点，先查询是否连通，如果连通，说明这是这对顶点第二次连通了，因此一定存在环。就可以判定这个图中存在环。如果不连通，那么就用Union操作把他们连通，并且丢到同一个群组里。
  • 读完所有边，如果都没出现环，则输出no，如果出现过环，则输出yes。

并查集写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*以下两个函数为并查集的两个函数,
在此前提上,要初始化所有的顶点的老大为自己,
即p[i]=i*/

int find(int* p, int tar) {
	int value = tar;
	while (p[value] != value) {
		value = p[value]; 
	}
  /*如果老大不是自己，说明还可以追溯到更加上级的老
  大，只有最高层级的老大才会指向自己*/
	return value; //返回tar的最终老大
}
void Union(int* p, int v1, int v2) {
	int r1 = find(p, v1); //找到两个端点的老大
	int r2 = find(p, v2);
	if (r1 != r2) //不相同的老大
		p[r2] = r1; 
    //随机选择一个老大，这里交换r1和r2结果完全一样
}

ok我们搞定了并查集之后，我们就可以直接完成这个题目了，上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//不再重复放上函数实现，直接调用
#include<iostream>
using namespace std;
int main() {
	int v,e,begin,end;
	cin >> v >> e;
	bool judge = false;
	int* p = new int[v];
	for (int i = 0; i < v; i++)
		p[i] = i;
	for (int i = 0; i < e; i++) {
		cin >> begin >> end;
		if (find(p, begin) != find(p, end))
			Union(p, begin, end);
		else 
			judge = true;
	}
	if (judge)
		cout << "yes";
	else
		cout << "no";
	return 0;
}

DFS解法

使用 DFS 可以判断一个无向图和有向中是否存在环。深度优先遍历图，如果在遍历的过程中，发现某个结点有一条边指向已访问过的结点，并且这个已访问过的结点不是上一步访问的结点，则表示存在环。

首先搞懂DFS的原理,看一下伪代码：

1
2
3
4
5
6
void DFS(顶点V){
  visited[V]=true;
  for(顶点V的所有邻接点W)
    if(!visited[W])
      DFS(W);
}

意思就是一次只走一条线，只要新的点有除了上一个点之外的未被访问过的其他邻接点，就往这个点走，并把这个点标记为已访问，直到没有符合条件的点了，退回到上一个点，去找上一个点的其他符合条件的点，直到退回到出发的位置。

怎么应用到本题呢，要找有没有环，就看看当前结点除了上一个点之外所有相邻的邻接点是不是都没有被访问过，如果存在被访问过的，那就说明存在环了。

对于我的修改，我会在注释里再做解释：

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
#include<iostream>
#include<vector>
using namespace std;
bool judge = false;
void DFS(int V, bool* visited,int v,int** map); //起始顶点为V，顶点个数为v
int main() {
	int v,e,begin,end;
	cin >> v >> e;
	bool* visited = new bool[v] {false};//全部初始化为false
	int** map = new int*[v];
	for (int i = 0; i < v; i++)
		map[i] = new int[v]{0};
	for (int i = 0; i < e; i++) {
		cin >> begin >> end;
		map[begin][end] = 1;//因为是无向图，所以都标记
		map[end][begin] = 1;
	}
	
	DFS(0, visited, v, map);//从0开始深度遍历
	if (judge)
		cout << "yes";
	else
		cout << "no";
	return 0;
}
void DFS(int V, bool* visited,int v,int** map){
	visited[V] = true; //把当前点标记为访问过
	for (int i = 0; i < v; i++) {
		if (map[V][i]) { //寻找邻居结点
			if (!visited[i]) { //找到邻居节点，还恰好未被访问
				//map[V][i] = 0;
				map[i][V] = 0; 
        //把这条边擦除，这个操作很重要！！在下面说
				DFS(i, visited, v, map); //继续深搜
			}
			else{
				judge = true; //如果邻居结点被访问过，则可以标记为有环，并退出循环
        break;//也可以不退出，退出的话省一些时间和空间
      }
		}
	}
}

为什么找到未被访问的邻居结点，后要把这条边擦除之后再对这个点进行深搜呢。因为如果后续回退到这个邻居点的时候，以再去寻找这个邻接点的邻居，一定包括我们当前的V，那么这个时候无论如何V都已经被访问过了，所以会进入else分支，判定为有环，实际上这条边已经走过一次了，我们把它当成了两条不同的边。

这么做的本质其实就是把map[i][j]和map[j][i]联系起来，只要map[i][j]走过了，实质上也就是map[j][i]走过了，为了防止再走一遍，我们抹除这条边。