Leetcode 207 Course Schedule 判断有向图是否有环

题目表述

There are a total of n courses you have to take, labeled from 0 to n-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 prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: 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.

有向图与拓扑排序

此题中，显然这些课程之间的相互关系构成了一个图数据结构。由于相互之间的课程存在依赖关系，所以这是一个有向图，而本题可以等价为判断一个有向图中是否存在环。

考虑这样一个结构
1 -> 2 -> 3 -> 1
这是一个环形结构，程序依次遍历1,2,3 而后在遍历最后一个结点时，发现这个结点已经被访问过，就发现了一个环。如果程序遍历完所有节点，没有发现上述的情况，就判断图中不存在环。因此这个问题被转化为一个拓扑排序问题。
关于拓扑排序，请参考leetcode210

BFS算法

BFS算法首先找到入度为0的结点（即不依赖于任何其他课程的结点），随后从图中删除该节点，并更新其它结点的入度。循环往复，直到没有新的节点为止。
1 -> 2 -> 3 -> 4 -> 2
初始找到结点1，NodeQueue=[1], 入度为[1:1, 2:2, 3:1, 4:1]
删除结点[1], 更新入度为 [2:1,3:1,4:1]
由于环导致的额外的入度，导致没有入度为0的结点，使得BFS提前结束，没有能够遍历所有的节点。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        int[][] edges   = new int[numCourses][numCourses];
        int count = 0;
        for (int[] pre:prerequisites){
            indegrees[pre[0]] = indegrees[pre[0]]+1;
            edges[pre[1]][pre[0]] = 1;
        }
        List<Integer> queue = new ArrayList<>();
        for (int i=0;i<numCourses;i++){
            //System.out.printf("Course:%d indegree:%d\n",i,indegrees[i]);
            if (indegrees[i]==0) {
                queue.add(i);
                indegrees[i] = -1;
            }
        }
        if (queue.size()==0) return false;
        while (count<numCourses&&!queue.isEmpty()){
            int number = queue.size();
            //System.out.printf("------------------\n");
            for (int i=0;i<number;i++){
                int course = queue.remove(0);
                //System.out.printf("Course:%d Count:%d\n",course,count);
                count++;
                for (int j=0;j<numCourses;j++){
                    if (edges[course][j]==1){
                        indegrees[j]--;
                        //System.out.printf("Update Course:%d Indegree:%d\n",j,indegrees[j]);
                    }
                }
            }
            for (int j=0;j<numCourses;j++){
                if (indegrees[j]==0) {
                    queue.add(j); 
                    indegrees[j]=-1;
                }
            }
        }
        if (queue.isEmpty()&&count<numCourses) return false;
        return true;
    }
}

DFS算法

本题中DFS算法的重点在于，在遍历过程中维护一个名为prev的数组，这个数组保存了当前所有已经遍历的结点，一旦下一个遍历的结点已经在prev中，则图中存在环。

class Solution {
    private List<List<Integer>> graph;
    private HashSet<Integer> visited;
    private boolean canFinishDFS(HashSet<Integer> prev, int course){
        if (visited.contains(course)) return true;
        prev.add(course);
        visited.add(course);
        for (int depCourse:graph.get(course)){
            if (prev.contains(depCourse)||!canFinishDFS(prev,depCourse)) return false;
        }
        prev.remove(course);
        return true;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        graph   = new ArrayList<List<Integer>>();
        visited = new HashSet<>();
        for (int i=0;i<numCourses;i++) graph.add(new ArrayList<Integer>());
        for (int[] pre:prerequisites){
            graph.get(pre[0]).add(pre[1]);
        }
        for (int i=0;i<numCourses;i++){
            //System.out.printf("Go through:%d\n",i);
            HashSet<Integer> prev = new HashSet<>();
            if (!canFinishDFS(prev,i)) return false;
        }
        return true;
    }
}