Leetcode 存档点（1）-- 课程表II

课程表II

这道题的基本思想是和拓扑排序相关联的，属于一个图的问题

图的存储结构

邻接矩阵表示法

邻接表表示法

拓扑排序

拓扑排序的过程就是在有向无环图中选择入度为0的节点，删除由它作为起点的邻边，重复这个过程，直到这个所有点都被输出。

BFS进行拓扑排序

初始

删除0

删除1

删除2

按照出度和入度的变化情况和通过队列的方式，很容易计算出一个拓扑排序的序列。这道题可以使用这样的BFS的方法进行拓扑排序，如果发现到最后，整个图没有遍历完成，并且没法输出节点，这时候说明出现了环，整个课程表问题没有办法解决。

DFS进行拓扑排序

使用DFS进行拓扑排序和图的排序方法大体相同，都主要使用的是深度优先搜索+visited数组记录排序的情况。但是由于visited数组中只有访问和未访问两个状态，而这道题是为了发现是否有环存在，所以要分成三个状态：

未访问- >访问此节点，标记为访问中，并且将节点将入栈中，弹出之后标记成已访问。
已访问 -> 跳过这个节点，访问下一个
访问中 -> 存在环，结束整个遍历搜索

在我们要完成这道题的编码的时候，我们选择邻接表是比较合适的。
代码如下：

public class 课程表II {
    //https://leetcode-cn.com/problems/course-schedule-ii/
    //一道拓扑排序的问题
     class Solution {
        private ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        private int visited[] ;
        private int status[] = {0,1,2};

        //如果遍历过程中出现了环的情况
        private boolean invalid = false;
        private LinkedList<Integer> stack = new LinkedList<>();
        //主要的dfs算法，使用栈保存迭代的情况
        private void dfs(int index){
            visited[index] = status[1];
            ArrayList<Integer> connected = graph.get(index);
            for (Integer sub : connected){
                //如果是未搜索的状态 直接进行递归
                if(visited[sub] == status[0]){
                    dfs(sub);
                    if(invalid) return;
                }
                //如果是搜索中的状态 出现了环路（最简单的情况是衔尾蛇）
                if(visited[sub] == status[1]){
                    invalid = true;
                    return;
                }
            }
            visited[index] = status[2];
            stack.add(index);
        }

        public int[] findOrder(int numCourses, int[][] prerequisites) {
            visited = new int[numCourses];
            //初始化graph
            for (int i = 0; i< numCourses ; i++) {
                graph.add(new ArrayList<>());
                visited[i] = 0;
            }

            for (int i = 0; i < prerequisites.length ; i++) {
                graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
            }
            //遍历每一个起
            for (int i = 0; i < numCourses; i++) {
                if(visited[i]== status[2])
                    continue;
                dfs(i);
            }

            if(invalid)
                return new int[0];

            int result[] = new int[numCourses];
            Collections.reverse(stack);
            for (int i = 0; i < stack.size(); i++) {
                result[i] = stack.get(i);
            }

            return result;
        }
    }

}