数据结构-拓扑排序笔记
一 拓扑排序是什么
一聊到 拓扑排序，一些录友可能会想这是排序，不会想到这是图论算法。
其实拓扑排序是经典的图论问题。
二 拓扑排序的应用场景
大学排课，例如 先上A课，才能上B课，上了B课才能上C课，上了A课才能上D课，等等一系列这样的依赖顺序。 问给规划出一条 完整的上课顺序。
拓扑排序在文件处理上也有应用，我们在做项目安装文件包的时候，经常发现 复杂的文件依赖关系， A依赖B，B依赖C，B依赖D，C依赖E 等等。
如果给出一条线性的依赖顺序来下载这些文件呢？
有录友想上面的例子都很简单啊，我一眼能给排序出来。
那如果上面的依赖关系是一百对呢，一千对甚至上万个依赖关系，这些依赖关系中可能还有循环依赖，你如何发现循环依赖呢，又如果排出线性顺序呢。
所以 拓扑排序就是专门解决这类问题的。
三 解决的问题
概括来说，给出一个 有向图，把这个有向图转成线性的排序 就叫拓扑排序。
当然拓扑排序也要检测这个有向图 是否有环，即存在循环依赖的情况，因为这种情况是不能做线性排序的。
所以拓扑排序也是图论中判断有向无环图的常用方法。
四 思路
做拓扑排序的话，如果肉眼去找开头的节点，一定能找到 节点0 吧，都知道要从节点0 开始。
但为什么我们能找到 节点0呢，因为我们肉眼看着 这个图就是从 节点0出发的。
作为出发节点，它有什么特征？
你看节点0 的入度 为0 出度为2， 也就是 没有边指向它，而它有两条边是指出去的。
节点的入度表示 有多少条边指向它，节点的出度表示有多少条边 从该节点出发。
所以当我们做拓扑排序的时候，应该优先找 入度为 0 的节点，只有入度为0，它才是出发节点。 理解以上内容很重要！
接下来我给出 拓扑排序的过程，其实就两步：
- 找到入度为0 的节点，加入结果集
- 将该节点从图中移除
循环以上两步，直到 所有节点都在图中被移除了。
结果集的顺序，就是我们想要的拓扑排序顺序 （结果集里顺序可能不唯一）
五 具体代码
117. 软件构建
import java.util.*;public class Main {public static void main(String[] args) {// 创建一个Scanner对象来读取用户输入Scanner input = new Scanner(System.in);// 读取顶点数和边数int n = input.nextInt(); // 顶点的数量int m = input.nextInt(); // 边的数量// 使用邻接表表示图，初始化每个顶点的邻接表为空List<List<Integer>> map = new ArrayList<>();for (int i = 0; i < n; i++) {map.add(new ArrayList<>());}// 初始化每个顶点的入度为0int[] inDegress = new int[n];// 读取边的信息，并更新邻接表和入度数组for (int i = 0; i < m; i++) {int s = input.nextInt(); // 边的起点int t = input.nextInt(); // 边的终点map.get(s).add(t); // 将终点添加到起点的邻接表中inDegress[t]++; // 增加终点的入度}// 创建一个队列，用于存储所有入度为0的顶点Deque<Integer> deque = new ArrayDeque<>();for (int i = 0; i < n; i++) {if (inDegress[i] == 0) {deque.addFirst(i); // 将入度为0的顶点加入队列}}// 创建一个列表，用于存储拓扑排序的结果List<Integer> ret = new ArrayList<>();// 进行拓扑排序while (!deque.isEmpty()) {int cur = deque.removeLast(); // 从队列中取出一个顶点ret.add(cur); // 将该顶点添加到排序结果中List<Integer> curList = map.get(cur); // 获取该顶点的所有邻接点for (int temp : curList) {inDegress[temp]--; // 减少邻接点的入度if (inDegress[temp] == 0) {deque.addFirst(temp); // 如果邻接点的入度变为0，则加入队列}}}// 检查是否所有顶点都被排序了，即图中是否存在环if (ret.size() == n) {// 如果所有顶点都被排序了，输出拓扑排序的结果for (int i = 0; i < n; i++) {System.out.print(ret.get(i));if (i < n - 1) {System.out.print(" "); // 顶点之间用空格分隔}}} else {// 如果存在环，则输出-1System.out.println(-1);}}
}