207. 课程表 (opens new window)

1.回溯+DFS

解题核心在于判断一个数列是否存在回环的问题。

• 哈希表保存所有课表，其中key为当前课程，value保存该课程的所有前置课程列表。
• 用currlist列表保存当前已搜索过的列表。需要考虑以下几种情况，同一门课程可能出现在不同分支，因此当前元素是否构成回环，不能通过currlist中是否出现过来判断。而要解决这个问题，每次当前课表元素进行搜索时进行回溯即可。这样就可以保证当前currlist中，仅保存一条分支回路出现的所有课程。

• 剪枝：visited保存前置课程不含有回路的所有节点。当前头节点在搜索每个子节点(前置课程)时，如果子节点的所有前置课程均不存在回路，用visited列表保存起来。后续在搜索其它节点时，如果该子节点再次被搜索(作为头结点)，那么此时就不需要再搜索下去了。

  例子：以上面图中的课程路径为例，4节点经过判定不含回路，那么就将该节点加入到visited中，下一次(其他分支或者是作为头结点)再遇上时，不需要再往下搜索。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        List<Integer> currlist = new ArrayList<>();
        List<Integer> visited = new ArrayList<>();
        //存储数据
        for (int i = 0; i < prerequisites.length; i++) {
            if (map.containsKey(prerequisites[i][0])) {
                List<Integer> temp = map.get(prerequisites[i][0]);
                temp.add(prerequisites[i][1]);
            } else {
                List<Integer> temp = new ArrayList<>();
                temp.add(prerequisites[i][1]);
                map.put(prerequisites[i][0], temp);
            }
        }
        //搜索
        for (Integer temp : map.keySet()) {
            currlist.add(temp);
            if (check(map, currlist, visited, temp)) return false;
            currlist.remove(temp);
        }
        return true;
    }
    public boolean check(HashMap<Integer, List<Integer>> map, List<Integer> currlist, List<Integer> visited, int curr) {
        //剪枝
        if (!map.containsKey(curr) || visited.contains(curr)) return false;
        List<Integer> list = map.get(curr);
        for (Integer integer : list) {
            if (currlist.contains(integer)) {
                return true;
            }
            currlist.add(integer);
            if (check(map, currlist, visited, integer)) return true;
            //回溯
            currlist.remove(integer);
        }
        visited.add(curr);
        return false;
    }
}

2.拓扑排序

节点存储

先上i才能上j，那么i的出度加一，j的入度加一。

• 每次把入度为0的节点放入队列
• 队列中的每当有一个节点出列，需要改变依赖该节点的所有节点的入度。
• 把新的入度为0的节点加入队列，重复2步骤

具体使用数据结构存储如下：

1️⃣开辟数组保存每个节点的入度大小，按照每个节点的索引进行存储。

2️⃣哈希表保存每个节点的出度指向的数组，其中key为节点的索引，value保存所有依赖key的所有节点。

如何判断修完所有的课程？

初始时，将所有入度为0的节点都加入到队列当中。当BFS遍历完所有的节点，如果数组中仍然存在入度不为0的节点，那么说明该节点构成回环。