这道题主要利用拓扑排序，判断该图是否有环，其中还会涉及到邻接矩阵。

原题

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]] 输出: true解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

输入: 2, [[1,0],[0,1]]输出: false解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

说明:

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。你可以假定输入的先决条件中没有重复的边。

提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。拓扑排序也可以通过 BFS 完成。

原题url：

解题

这是我第一次遇到图相关的题目，讲道理，有向图、无向图、出度、入度之类的概念还能记得，但是拓扑排序、邻接矩阵、逆邻接矩阵却只是知道有这么一个概念，但具体内容也已经忘光了。我会在下面的解题过程中为大家呈现这些概念。

先介绍一下拓扑排序：

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：1. 每个顶点出现且只出现一次。2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

从上面的概念中可以看出，这道题目就是要判断给定的图是否是有向无环图，也就是其是否有拓扑排序。

求一个图是否有拓扑排序，我们一般有两种办法：广度优先搜索 + 邻接矩阵、深度优先搜索 + 逆邻接矩阵。接下来我们逐一来为大家分析：

广度优先搜索 + 邻接矩阵

首先看一下什么是邻接矩阵：

在图论中，邻接矩阵（英语：adjacency matrix）是表示一种图结构的常用表示方法。它用数字方阵记录各点之间是否有边相连，数字的大小可以表示边的权值大小。

这么看有点抽象，简单点说：就是一个图中各个节点的后继节点链表。

举个例子：

这样一个图，其邻接矩阵为：

1 -> 2 -> 3 -> null2 -> 4 -> null3 -> 4 -> null4 -> null

好了，弄懂了邻接矩阵，我们来想想如何使用广度优先搜索？

假设有向图无环，那么从入度为 0 的点，依次删除，这里并不是真正意义上的删除，只是如果该节点消失后，其后继节点的入度需要减1，此时再判断是否又有新的入度为0的节点，如果最终所有节点都会被减到0，那么说明有向图无环，让我们看一下代码：

class Solution {    public boolean canFinish(int numCourses, int[][] prerequisites) {        // 利用入度表和DFS进行拓扑排序        // 下标i对应的节点，其入度的数组        int[] indegressArray = new int[numCourses];        // key:节点i，value:其所有出度节点        Map<Integer, List<Integer>> map = new HashMap<>(numCourses * 4 / 3 + 1);        for (int[] pre : prerequisites) {            indegressArray[pre[0]] += 1;            List<Integer> list = map.get(pre[1]);            if (list == null) {                list = new LinkedList<>();                map.put(pre[1], list);            }            list.add(pre[0]);        }        // 将入度为0的入队列        LinkedList<Integer> list = new LinkedList<>();        for (int i = 0; i < indegressArray.length; i++) {            int indegress = indegressArray[i];            if (indegress != 0) {                continue;            }            list.add(i);        }        while (!list.isEmpty()) {            // 获取第一个节点，并将这个节点"删除"            int node = list.removeFirst();            numCourses--;            // 那么以node作为前驱节点的节点，其入度-1            List<Integer> preList = map.get(node);            if (preList == null) {                continue;            }            for (Integer suffixNode : preList) {                indegressArray[suffixNode] -= 1;                // 如果该节点入度减为0，则也入队                if (indegressArray[suffixNode] == 0) {                    list.add(suffixNode);                }            }        }        // 如果最终所有节点都入队并且也出队，那么说明该图无环。        return numCourses == 0;    }}

提交OK，执行用时：8 ms，内存消耗：45 MB，执行用时只战胜了84.74%的 java 提交记录，我们再优化优化试试。

广度优先搜索 + 邻接矩阵 优化

map 虽然理论上查找速度为 O(1)，但需要先计算 hash 值，而数组的话，其获取地址是根据下标的。而我们这里的数字是连续的，并且从 0 开始，因此很适用数组的情况，因此做一个改造：

class Solution {    public boolean canFinish(int numCourses, int[][] prerequisites) {        // 利用入度表DFS进行拓扑排序        // 下标i对应的节点，其入度的数组        int[] indegressArray = new int[numCourses];        // 邻接矩阵，数组下标:节点i，list:其所有后继节点        List<Integer>[] adjacencyMatrix = new LinkedList[numCourses];        for (int[] pre : prerequisites) {            // 入度表相应节点的入度+1            indegressArray[pre[0]] += 1;            // 邻接矩阵            List<Integer> list = adjacencyMatrix[pre[1]];            if (list == null) {                list = new LinkedList<>();                adjacencyMatrix[pre[1]] = list;            }            list.add(pre[0]);        }        // 将入度为0的入队列        LinkedList<Integer> list = new LinkedList<>();        for (int i = 0; i < indegressArray.length; i++) {            int indegress = indegressArray[i];            if (indegress != 0) {                continue;            }            list.add(i);        }        while (!list.isEmpty()) {            // 获取第一个节点，并将这个节点"删除"            int node = list.removeFirst();            numCourses--;            // 那么以node作为前驱节点的后继节点，入度-1            List<Integer> preList = adjacencyMatrix[node];            if (preList == null) {                continue;            }            for (Integer prefixNode : preList) {                indegressArray[prefixNode] -= 1;                // 如果该节点入度减为0，则也入队                if (indegressArray[prefixNode] == 0) {                    list.add(prefixNode);                }            }        }        // 如果最终所有节点都入队并且也出队，那么说明该图无环。        return numCourses == 0;    }}

提交OK，执行用时：5 ms，内存消耗：45 MB，执行用时战胜了94.01%的 java 提交记录，应该差不多了。

深度优先搜索

既然知道了邻接矩阵，那么逆连接矩阵就是指的各个节点的前驱节点链表。还是以之前的那个例子：

这样一个图，其逆逆邻接矩阵为：

1 -> null2 -> 1 -> null3 -> 1 -> null4 -> 2 -> 3 -> null

那么如何进行深度优先遍历呢？也就是以一个节点出发，访问其相邻节点，一直遍历下去，如果发现一个节点被访问两次，说明有环，那么返回失败，否则就标记该节点已经全部访问完成。当访问完全部节点成功后，说明有向图无环。

这么一看，深度优先遍历的时候，其实只要保证相邻即可，无所谓邻接矩阵还是逆邻接矩阵。

我们来看看代码：

class Solution {    public boolean canFinish(int numCourses, int[][] prerequisites) {        // 利用逆邻接矩阵，进行深度优先搜索        HashSet<Integer>[] inadjacencyMatrix = new HashSet[numCourses];        for (int i = 0; i < numCourses; i++) {            inadjacencyMatrix[i] = new HashSet<>();        }        // 构造逆连接矩阵（每个节点的所有后继节点）        for (int[] array : prerequisites) {            inadjacencyMatrix[array[1]].add(array[0]);        }        // 所有节点的被使用情况，如果正在使用的节点，再次被访问，说明有环        // 0：未使用；1：正在使用；2：已经使用完成；        int[] used = new int[numCourses];        for (int i = 0; i < numCourses; i++) {            if (dfs(i, inadjacencyMatrix, used)) {                return false;            }        }        return true;    }    public boolean dfs(int index, HashSet<Integer>[] inadjacencyMatrix, int[] used) {        // 如果当前节点已经处于正在被访问的状态，现在又再次访问，说明有环        if (used[index] == 1) {            return true;        }        // 如果当前节点已经访问结束，则可以不用再次被访问        if (used[index] == 2) {            return false;        }        // used[index] == 0，说明该节点从未被访问过，那么现在开始访问该节点        used[index] = 1;        // 深度遍历该节点的后继节点        HashSet<Integer> suffixNodes = inadjacencyMatrix[index];        for (int suffixNode : suffixNodes) {            if (dfs(suffixNode, inadjacencyMatrix, used)) {                return true;            }        }        // 深度遍历完成该节点，直接结束        used[index] = 2;        return false;    }}

提交OK，执行用时：8 ms，内存消耗：44.6 MB，优化的话，暂时并没有想到好方法。

总结

以上就是这道题目我的解答过程了，不知道大家是否理解了。这也是我第一次解决图相关的题目，涉及的知识点有些多，需要好好消化。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。

公众号：健程之道