数据结构-拓扑排序笔记
一 拓扑排序是什么
一聊到 拓扑排序,一些录友可能会想这是排序,不会想到这是图论算法。
其实拓扑排序是经典的图论问题。
二 拓扑排序的应用场景
大学排课,例如 先上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);}}
}