Java高阶数据结构 & 图补充-拓扑排序
1. 什么是拓扑排序
图片来源：简单、快速地带你了解图论以及拓扑排序！_哔哩哔哩_bilibili
- 讲得很好哦！
这里我以羊了个羊小游戏这款砖块消除类小游戏为例：
有一个规则：
- 当上层砖块覆盖下层砖块的时候，下层砖块不可以被选中移动（暗）
- 上层砖块移走后，下层砖块才能被移动（亮）
则可以用如下图表示这种逻辑结构：
- A->B，代表A覆盖B
- 即一种无环不带权有向图
- 带回路的话，那么这个顶点就相当于自己覆盖了自己，不合理
- 无向的话，一条边则是双向的，同1不合理
- 箭头代表覆盖关系，权值不重要
那么我们给每个砖块一个layer值：
要求：
- layer值大的砖块显示上，覆盖layer值小的砖块
- 即A->B，layer(A) > layer(B)
在开发过程中需要这个layer，至于用处是什么，不做解释，这里这不是重点。
- 至于这款游戏的原理，感兴趣的可以去网上找找资料研究一下
我们只需要找到一个序列，保证上方的覆盖者要在被覆盖者前方，再为其安排一个递减的序列
那么问题是：如何生成这个序列呢？
- 这个排序，就叫做 “拓扑排序”
类似的，如果你需要学习一系列的课程，那么一些知识一定需要另一些知识作为基础~
- 而显然的，符合实际的是：这种序列不应该唯一
- 学习路径肯定不一定单一呀~
- 事实上也如此~
- 一个图的拓扑排序很有可能有多解
2. 拓扑排序算法思想-卡恩算法
- 本文章用邻接表的存储结果！
基础知识传送门：Java高阶数据结构 & 图 & 图的表示与遍历_s:103的博客-CSDN博客
例子：
前面提到，如果成环则没有拓扑序列，那么我们也可以通过能否拓扑排序，来判断一个图是否带环
- 这也算是拓扑排序的一个额外得到功能吧
这里只讲解一种简单直接的算法，卡恩算法
- 重点在于每个顶点的入度
步骤：
- 遍历一遍邻接表，计算所有顶点的入度
- 挑选一个入度为0的顶点，并输出
- 刚才挑中的顶以及其指向的顶点的入度都减1
- -1的入度代表此顶点被删除
- 挑选一个入度为0的顶点，并输出
- 刚才挑中的顶以及其指向的顶点的入度都减1
- 重复这个操作，直到所有顶点都被删除（入度都为-1）
- 如果最终是因为没有入度为0的顶点而不是全部顶点都被删除而停止的循环，则说明存在环
疑问：
1. 你很快会意识到，如果出现多个入度为0的顶点，应该怎么办？
答：先挑选谁都无所谓，因为这两个入度为0的顶点，是一种并列的关系，不会相互影响。即使他们有可能分支下去会有公共顶点，这也不会导致“乱了规则”的现象，因为“汇聚的第一个公共顶点”入度至少为2，只有其入度为0的时候才能被选中
- 也就是说，只有如果先选中的入度为0的顶点输出后，诞生新的入度为0的顶点，一定也与原来入度为0的顶点也是并列
- 这也是序列不唯一的原因~
2. 为什么入度为0的顶点先被选中？
答：这很显然，入度为0，代表没人指向它
- 也就是说，它没被覆盖，而只覆盖别人！
- 万物之源
算法复杂度分析：
- 每个顶点和每条边都刚好被访问一次
V因为顶点数，E为边数
- 则时间复杂度为O(V + E)
动图演示：
3. 拓扑排序代码实现
- 我这边直接延用之前实现邻接表的代码（自制API）
- 获取：Java高阶数据结构 & 图 & 图的表示与遍历_s:103的博客-CSDN博客
以下代码就不做过多解释了，完全依照刚才的算法思想~
3.1 遍历链表计算入度
//获取所有顶点的入度 public int[] getDevs() { int n = arrayV.length; int[] arr = new int[n]; for (int i = 0; i < n; i++) { Node cur = edgeList.get(i); while(cur != null) { arr[cur.dest]++; cur = cur.next; } } return arr; }
3.2 挑选一个入度为0的顶点
- 你也可以结合isVisted数组（标记数组）和堆去存储，节约时间
- 这里用最简单的遍历法
public int getFirstZero(int[] arr) { for (int i = 0; i < arr.length; i++) { if(arr[i] == 0) { return i; } } return -1; }
3.3 输出顶点
- 这里我将顶点输出到队列里了
public void outputV(int index, int[] arr, Queue<Character> queue) { queue.offer(arrayV[index]); arr[index]--; Node cur = edgeList.get(index); while(cur != null) { arr[cur.dest]--; cur = cur.next; } }
3.4 判断循环结束是否为全-1
public boolean isContainCir(int[] arr) { for (int i = 0; i < arr.length; i++) { if(arr[i] != -1) { return true; } } return false; }
3.4 kahn方法
public boolean kahn(Queue<Character> queue) { int[] arr = getDevs(); int index = getFirstZero(arr); while(index != -1) { outputV(index, arr, queue); index = getFirstZero(arr); } return isContainCir(arr); }
3.5 测试
public static void main(String[] args) { //定义与构建图 char[] chars = "012345678".toCharArray(); GraphByList graph = new GraphByList(chars.length, true); graph.initArrayV(chars); graph.addEdge('0', '1', 1); graph.addEdge('0', '2', 1); graph.addEdge('1', '3', 1); graph.addEdge('2', '3', 1); graph.addEdge('2', '4', 1); graph.addEdge('4', '3', 1); graph.addEdge('6', '0', 1); graph.addEdge('7', '0', 1); graph.addEdge('7', '6', 1); graph.addEdge('8', '5', 1); //定义队列 Queue<Character> queue = new LinkedList<>(); boolean flag = graph.kahn(queue); System.out.println(flag ? "带环" : "不带环"); System.out.println(queue); }
