基本概念
拓扑排序的英文名是 Topological sorting。
拓扑排序要解决的问题是给一个图的所有节点排序。有向无环图才有拓扑排序，非有向无环图没有。
换句话说，拓扑排序必须满足以下条件
图必须是一个无环有向图。序列必须满足的条件：
- 每个顶点出现且只出现一次。
- 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
实战
我们已 leetcode 上面的一道算法题目作为切入点进行讲解。
leeocode 210: https://leetcode-cn.com/problems/course-schedule-ii/
eg: 现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1
输入: 2, [[1,0]] 输出: [0,1] 解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2
输入: 4, [[1,0],[2,0],[3,1],[3,2]] 输出: [0,1,2,3] or [0,2,1,3] 解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
这道题，很明显，看起来可以有有向无环图的解法来解决
BFS 算法
题目分析
我们首先引入有向图 描述依赖关系
示例：假设 n = 6，先决条件表：[ [3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4] ]
- 0, 1, 2 没有先修课，可以直接选。其余的，都要先修 2 门课
- 我们用 有向图 描述这种 依赖关系 (做事的先后关系)：
在有向图中，我们知道，有入度和出度概念：
如果存在一条有向边 A --> B，则这条边给 A 增加了 1 个出度，给 B 增加了 1 个入度。所以顶点 0、1、2 的 入度为 0。 顶点 3、4、5 的 入度为 2
BFS 前准备工作
- 我们关心 课程的入度 —— 该值要被减，要被监控
- 我们关心 课程之间的依赖关系 —— 选这门课会减小哪些课的入度
- 因此我们需要合适的数据结构，去存储这些关系,这个可以通过哈希表
解题思路
- 维护一个 queue，里面都是入度为 0 的课程
- 选择一门课，就让它出列，同时 查看哈希表，看它 对应哪些后续课
- 将这些后续课的 入度 - 1，如果有减至 0 的，就将它推入 queue
- 不再有新的入度 0 的课入列 时，此时 queue 为空，退出循环
private class Solution { public int[] findOrder(int num, int[][] prerequisites) { // 计算所有节点的入度，这里用数组代表哈希表，key 是 index， value 是 inDegree[index].实际开发当中，用 HashMap 比较灵活 int[] inDegree = new int[num]; for (int[] array : prerequisites) { inDegree[array[0]]++; } // 找出所有入度为 0 的点，加入到队列当中 Queue<Integer> queue = new ArrayDeque<>(); for (int i = 0; i < inDegree.length; i++) { if (inDegree[i] == 0) { queue.add(i); } } ArrayList<Integer> result = new ArrayList<>(); while (!queue.isEmpty()) { Integer key = queue.poll(); result.add(key); // 遍历所有课程 for (int[] p : prerequisites) { // 改课程依赖于当前课程 key if (key == p[1]) { // 入度减一 inDegree[p[0]]--; if (inDegree[p[0]] == 0) { queue.offer(p[0]); // 加入到队列当中 } } } } // 数量不相等，说明存在环 if (result.size() != num) { return new int[0]; } int[] array = new int[num]; int index = 0; for (int i : result) { array[index++] = i; } return array; } }
DFS 解法
算法思想
- 对图执行深度优先搜索。
- 在执行深度优先搜索时，若某个顶点不能继续前进，即顶点的出度为0，则将此顶点入栈。
- 最后得到栈中顺序的逆序即为拓扑排序顺序。
// 方法 2：邻接矩阵 + DFS 由于用的数组，每次都要遍历，效率比较低 public int[] findOrder(int numCourses, int[][] prerequisites) { if (numCourses == 0) return new int[0]; // 建立邻接矩阵 int[][] graph = new int[numCourses][numCourses]; for (int[] p : prerequisites) { graph[p[1]][p[0]] = 1; } // 记录访问状态的数组，访问过了标记 -1，正在访问标记 1，还未访问标记 0 int[] status = new int[numCourses]; Stack<Integer> stack = new Stack<>(); // 用栈保存访问序列 for (int i = 0; i < numCourses; i++) { if (!dfs(graph, status, i, stack)) return new int[0]; // 只要存在环就返回 } int[] res = new int[numCourses]; for (int i = 0; i < numCourses; i++) { res[i] = stack.pop(); } return res; } private boolean dfs(int[][] graph, int[] status, int i, Stack<Integer> stack) { if (status[i] == 1) return false; // 当前节点在此次 dfs 中正在访问，说明存在环 if (status[i] == -1) return true; status[i] = 1; for (int j = 0; j < graph.length; j++) { // dfs 访问当前课程的后续课程，看是否存在环 if (graph[i][j] == 1 && !dfs(graph, status, j, stack)) return false; } status[i] = -1; // 标记为已访问 stack.push(i); return true; }
总结
这篇博客从实战的角度出发，介绍了有向无环图的两种解法，入度表法和 DFS 法。其中，入度表法很重要，必须掌握。下一篇，我们将从 项目实战的角度来讲解，怎样搭建一个有向无环图的通用框架，敬请期待。
ps
AnchorTask 源码已经更新到 github，AnchorTask，下一篇，将输出 AnchorTask 使用说明，敬请期待。
