8-4，判断有向图是否有圈的两种常用方法

有向无环图(Directed Acycling Graph)：是图中没有回路(环)的有向图。是一类具有代表性的图，主要用于研究工程项目的工序问题、工程时间进度问题等。

那么首先，讨论判断一个有向图是否有圈的算法，以及他的应用。

1. 拓扑排序

算法描述：

对一个有向无圈图，首先找出所有的入度为0的点，访问、操作这些点；
删除所有的入度为0的点，以及所有的和这些点相连的边；
重复1、2步操作直到没有入度为0的点，对一个有向无圈图来说，最后一定会一个点都不剩了，否则，说明这个有向图是有圈的。

2. DFS

算法描述：

规定，对以访问的点设1，正在访问的点设0，未访问的点设-1；
从任意点出发，对该点深度优先搜索，如果在搜索的过程中发现下一个点为0，出现了重复访问，说明有圈；
当所有的点都变成1，仍旧没有出现重复访问，说明没有圈。

3. 应用

在选择课程的时候，有的课程必须要求有先修课程，那么将这些课程的关系抽象出来即是有向无圈图。
例题可以参考上一篇文章：课程表(一)

在这里采用DFS重新实现该算法：

class Solution{
public:
	vector<vector<int>> preList;//存储能从该节点直接到达的节点
	vector<int> vis;//标记访问信息
	bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
		if(prerequisites.size() == 0)
			return true;
		vis.resize(numCourses, -1);
		preList.resize(numCourses);
		for(int i=0; i<prerequisites.size(); i++){
			int pre = prerequisites[i][0];
			int next = prerequisites[i][1];
			preList[pre].push_back(next);
		}
		for(int i=0; i<numCourses; i++){
			if(vis[i] == -1 && !DFS(i))//-1表示尚未访问过
				return false;
		}
		return true;
	}
	bool DFS(int node){
		if(vis[node] == 0)//0表示重复访问
			return false;
		vis[node] = 0;//0正在访问
		for(int i=0; i<preList[node].size(); i++){
			if(!DFS(preList[node][i]))
				return false;
		}
		vis[node] = 1;//1表示访问过了
		return true;
	}
};