力扣207——课程表
这道题主要利用拓扑排序，判断该图是否有环，其中还会涉及到邻接矩阵。
原题
现在你总共有 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：https://my.openwrite.cn/user/article/write
解题
这是我第一次遇到图相关的题目，讲道理，有向图、无向图、出度、入度之类的概念还能记得，但是拓扑排序、邻接矩阵、逆邻接矩阵却只是知道有这么一个概念，但具体内容也已经忘光了。我会在下面的解题过程中为大家呈现这些概念。
先介绍一下拓扑排序：
在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。
从上面的概念中可以看出，这道题目就是要判断给定的图是否是有向无环图，也就是其是否有拓扑排序。
求一个图是否有拓扑排序，我们一般有两种办法：广度优先搜索 + 邻接矩阵、深度优先搜索 + 逆邻接矩阵。接下来我们逐一来为大家分析：
广度优先搜索 + 邻接矩阵
首先看一下什么是邻接矩阵：
在图论中，邻接矩阵（英语：adjacency matrix）是表示一种图结构的常用表示方法。它用数字方阵记录各点之间是否有边相连，数字的大小可以表示边的权值大小。
这么看有点抽象，简单点说：就是一个图中各个节点的后继节点链表。
举个例子：
这样一个图，其邻接矩阵为：
1 -> 2 -> 3 -> null
2 -> 4 -> null
3 -> 4 -> null
4 -> 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 -> null
2 -> 1 -> null
3 -> 1 -> null
4 -> 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，优化的话，暂时并没有想到好方法。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这也是我第一次解决图相关的题目，涉及的知识点有些多，需要好好消化。
有兴趣的话可以访问我的博客或者关注我的公众号，说不定会有意外的惊喜。
https://death00.github.io/
公众号：健程之道