无向图判定是否存在环

缘起

需求是判定一个无向图是否存在环

算法的核心很简单, 就是dfs. 只是dfs的时候额外做点事情. 

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
#include "stdafx.h"
#include <iostream>
#include <stack>
#include <vector>
#pragma warning(disable:4996) // 防止scanf 等不带_s的api报错

#define LOCAL
using namespace std;

#define MAX_VERTEX_NUM 10
typedef vector<int>::iterator it; // 定义迭代器 


struct Graph
{
	vector<int> vertex[MAX_VERTEX_NUM]; // 二维数组
	int vertexnum; // 顶点的个数
	bool isvisited[MAX_VERTEX_NUM];
	Graph()
	{
		puts("请输入顶点的个数.\n");
		scanf("%d", &vertexnum);
		puts("请输入各边");
		int start, end;
		while(~scanf("%d%d", &start, &end))
		{
			vertex[start].push_back(end); // 因为是无向图, 所以要做两次
			vertex[end].push_back(start);
		}
	}

	// 判断无向图（未必连通）中是否存在环 返回false表示有环, 返回true表示无环
	bool circle()
	{
		memset(isvisited, 0, sizeof(isvisited));
		for (int i = 0; i<vertexnum;i++)
		{
			if (!isvisited[i])
			{
				isvisited[i] = true;
				if (!dfs(i, -1))return false;  // 开启遍历各个连通分支之旅
			}
			
		}
		return true;
	}

private:
	// 返回true 表示无环, false 表示有环, cur 是当前节点, father是来到cur之前的那个节点
	bool dfs(int cur, int father)
	{
		for (int i = 0; i<vertexnum; i++)
		{
			if (isconnected(cur, i)) // 前提是在无向图上从cur 可以到达i, 不然都免谈
			{
				if (i!=father && isvisited[i]) return false; // 如果i不是cur的父亲, 但是曾经访问过, 则一定存在环
				else if(isvisited[i])continue; // 如果 i=father, 这个不算环的
				else // i没被访问过
				{
					isvisited[i] = true;
					if (!dfs(i,cur)) return false; // 如果沿着一条路径深搜下去找到了环, 就直接返回false, 反之没找到的话, 并不能就此断定没有环, 还要看别的路径的结果
				}
			}
		}
		return true; // 如果上面都没有找到环, 就返回true
	}

	// 无向图上 是否存在 (i,j)这条边
	bool isconnected(int i, int j)
	{
		for (it x = vertex[i].begin(); x!=vertex[i].end(); x++)if (*x == j)return true;
		return false;
	}
};



int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	Graph g;
	cout << (g.circle()?"无环":"有环")<<endl;
	return 0;
}