DAG判定的除拓扑序之外的另一种方法

缘起

在参考【1】和【2】中，我们分别提出了无向图是否有环的判定和有向图是否有环的判定（亦即是否是DAG图）. 并指出了有向图是否有环和无向图是否有环的判定方法是不一样的. 因为有向图在遍历过程中边的终点有被遍历到并不能断言存在环，因为这两个顶点很可能在不同的dfs树上. 即这条边仅仅是横叉边. 但是无向图就不一样,无向图的边没有方向. 不存在存在边相连而不在一个连通分支的情形. 所以才有了另辟蹊径的拓扑序判定DAG的方法. 但是本文将介绍依旧是dfs的架子来判定有向图是否含环.

分析

算法的核心是

1
如果在一条搜索路径上搜到了已经访问过的节点的话，则有向图一定含环.

注意, 和无向图不一样, 无向图是

1
如果在遍历途中搜到了已经访问过的节点并且它还不是其父节点的话，则一定含环.

注意措辞, 前者是搜索路径，后者是遍历. 有什么不同么? 有! 落到细节就是前者是标志位要改回来，但是后者标志位不要改回来! 但是为什么要有下面的mark数组呢？ 目的就是用于标记不同的dfs搜索树. 因为如果一棵已经搜过了的dfs树没有发现环的话, 从别的dfs搜索树搜到这棵搜索树上的某个节点就可以停止了. 因为你在纸上比划一下就知道这条路不可能构成环了，否则之前的dfs树就会发现这个环了. 所以这个mark数组和isvisited数组不一样. 前者是不要改回来的, 避免重复搜. 后者要改回来的, 用于取得不同的搜索路径.

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
#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];
	bool mark[MAX_VERTEX_NUM];
	Graph()
	{
		puts("请输入顶点的个数.\n");
		scanf("%d", &vertexnum);
		puts("请输入各边起点和终点,起点在前,终点在后");
		int start, end;
		while(~scanf("%d%d", &start, &end))vertex[start].push_back(end);
	}

	bool circle() // 有向图是否有环, true 表示有环,false表示无环
	{
		memset(isvisited, 0, sizeof(isvisited));
		memset(mark, 0, sizeof(mark));
		for (int i =0;i<vertexnum;i++)
		{
			if (dfs(i)) 
			{
				return true;
			}
		}
		return false;
	}

private:

	// 从i 出发, 判定是否存在环
	bool dfs(int i)
	{
		if (isvisited[i])
		{
			return true; // 如果在一条搜索路径上遇到了已经访问过的节点,则一定是存在环的, 注意, 这个判断和下面的mark的判断不能反序,因为只有在没有访问过的情况下，mark了才可以直接断定没有环,不然的话, 如果isvisited[i]为true的话,则mark[i为true是显然的(看代码56行).
		}
		if (mark[i])
		{
			return false; // 因为已经搜过了, 前面没搜到环的话, 这里也不可能搜到环, 所以直接剪枝. 返回无环.
		}
		mark[i] = isvisited[i] = true; // 标记为已访问
		for (int j = 0; j<vertexnum;j++)
		{
			if (isconnected(i,j)) // 注意, 不需要对mark和isvisited进行判断, 因为这些都是放在前面做判断的
			{
				if (dfs(j)) // 如果有一条路发现有环的话, 就返回true
				{
					return true;
				}
			}
		}
		isvisited[i] = false; // 改回来，要记得改回来. 因为是在做搜索路径, 而不是遍历
		return false; // 说明无环
	}

	// 有向图上 是否存在(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;
}

参考

【1】https://yfsyfs.github.io/2019/05/21/%E6%97%A0%E5%90%91%E5%9B%BE%E5%88%A4%E5%AE%9A%E6%98%AF%E5%90%A6%E5%AD%98%E5%9C%A8%E7%8E%AF/

【2】https://yfsyfs.github.io/2019/05/21/%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F/