Course Schedule:判断有向图是否有环
2018-02-01 14:29:21         来源：小雄鹿的博客

Course Schedule:判断有向图是否有环。

There are a total ofncourses you have to take, labeled from`0ton - 1.`

`Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:[0,1]`

`Given the total number of courses and a list of prerequisitepairs, is it possible for you to finish all courses?`

`For example:`

``2, [[1,0]]``

`There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.`

``2, [[1,0],[0,1]]``

`There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.`

`Note:`

1. `The input prerequisites is a graph represented bya list of edges, not adjacency matrices. Read more abouthow a graph is represented.You may assume that there are no duplicate edges in the input prerequisites. `

`click to show more hints.`

`Hints: `
1. `This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.Topological Sort via DFS- A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.Topological sort could also be done viaBFS. 思路：提示里已经说得很明白了，有dfs或者bfs做拓扑排序判断是否有环。 `

`我是用dfs，假设每个定点有三种状态：未访问、正在访问、访问完成。当沿着一条边深度优先访问时碰到了正在访问的顶点，则说明有环，否则未发现环。访问结束记得将访问中的状态改为访问完成。`

``````class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if(numCourses == 0) return true;
if(prerequisites.length == 0) return true;
HashMap> graph = new HashMap>();
for(int[] edge:prerequisites){//构造图
if(graph.get(edge[1]) == null){
ArrayList l = new ArrayList();
graph.put(edge[1],l);
}else{
}
}
//dfs判断图是否有环，采用三种颜色：0 未访问 、1 正在访问 、 2 已访问
int[] state = new int[numCourses];
boolean res = true;
for(int i = 0 ;i < numCourses; i++ ){
res = res && dfs(graph,state,i);
if(res == false) return false;
}
return res;
}

public boolean dfs(HashMap> graph,int[] state,int vertex){
if(state[vertex] == 1){
return false;
}else if(state[vertex] == 2){
return true;
}else{
state[vertex] = 1;
List edges = graph.get(vertex);
if(edges == null) {
state[vertex] = 2;
return true;
}
boolean res = true;
for(int v : edges){
res = res && dfs(graph,state,v);
}
state[vertex] = 2;
return res;
}
}
}``````
`bfs的方式则从入度的角度考虑。类似于人工考察是否有环，先将入度为0的顶点排除，且将之指向的顶点的入度减1，不断重复，直到所有顶点均被排除则证明无环，否则便是无环。下面是jiayuliu961的答案。比我的简洁多了。`
``````public boolean canFinish(int numCourses, int[][] prerequisites) {
int[][] matrix = new int[numCourses][numCourses]; // i -> j
int[] indegree = new int[numCourses];

for (int i=0; i queue = new LinkedList();
for (int i=0; i
``````