拓扑排序
适用范围：要求有向图，且有入度为0的节点，且没有环。
给出一个有向图，如何确定访问节点的顺序，并能保证所有的都被访问到，拓扑排序就是来解决这个问题的。
举个例子
假定有向图如下：
网络异常，图片无法展示
|
- 先确定入度为0的点，为A，这个点在拓扑排序中是排在最前面的
- 确定好A点之后，将A点从图中抹去，剩下B、C、D三个点，可以确定拓扑排序的第二个点是B（入度为0）
- 同样将B点从图中抹去，可以依次确定拓扑排序的第三、四个点是C、D
拓扑排序的思路
给出一个有向图，依次找出入度为0的点，就可以确定出访问节点的顺序
public class TopologySort{ public static List<Node> sortedTopology(Grapgh grapgh){ // key: 某一个node // value：剩余的入度 HashMap<Node, Integer> inMap = new HashMap<>(); // 入度为0的点，才能进这个队列 Queue<Node> zeroInQueue = new LinkedList<>(); for(Node node: graph.nodes.values()){ inMap.put(node, node.in); if(node.in == 0){ zeroInQueue.add(node): } } // 拓扑排序的结果，依次加入result List<Node> result = new ArrayList<>(); while(!zeroInQueue.isEmpty()){ Node cur = zeroInQueue.poll(); result.add(cur); for(Node next: cur.nexts){ inMap.put(next, inMap.get(next)-1); if(inMao.get(next)==0){ zeroInQueue.add(next); } } } return result; } } 复制代码
Leetcode-207. 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
分析
本题的选课，有种依赖关系，可以用有向无环图来描述依赖关系：
网络异常，图片无法展示
|
这里我们需要把一个有向无环图转成线性的排序，这就是拓扑排序。
拓扑排序中有两个概念：入度和出度。
在这里，入度为0就表示这门课不依赖别的课，可以直接去上课。因为在选课时，我们就先去学那个入度为0的课程。学完这个课程之后，就可以再去学别的课程。
步骤
- 让入度为 0 的课入列，它们是能直接选的课。
- 然后逐个出列，出列代表着课被选，同时清除该课的相关联系，也就是减小相关课的入度。
- 如果相关课的入度新变为 0，安排它入列、再出列……直到没有入度为 0 的课可入列。
- 当遍历完成时，如果仍有课的入度不为 0，无法被选，完成不了所有课。否则，能找到一种顺序把所有课上完。
代码实现
const canFinish = (numCourses, prerequisites) => { const inDegree = new Array(numCourses).fill(0); // 入度数组 const map = {}; // 邻接表 for (let i = 0; i < prerequisites.length; i++) { inDegree[prerequisites[i][0]]++; // 求课的初始入度值 if (map[prerequisites[i][1]]) { // 当前课已经存在于邻接表 map[prerequisites[i][1]].push(prerequisites[i][0]); // 添加依赖它的后续课 } else { // 当前课不存在于邻接表 map[prerequisites[i][1]] = [prerequisites[i][0]]; } } const queue = []; for (let i = 0; i < inDegree.length; i++) { // 所有入度为0的课入列 if (inDegree[i] == 0) queue.push(i); } let count = 0; while (queue.length) { const selected = queue.shift(); // 当前选的课，出列 count++; // 选课数+1 const toEnQueue = map[selected]; // 获取这门课对应的后续课 if (toEnQueue && toEnQueue.length) { // 确实有后续课 for (let i = 0; i < toEnQueue.length; i++) { inDegree[toEnQueue[i]]--; // 依赖它的后续课的入度-1 if (inDegree[toEnQueue[i]] == 0) { // 如果因此减为0，入列 queue.push(toEnQueue[i]); } } } } return count == numCourses; // 选了的课等于总课数，true，否则false }; 复制代码
