目录
介绍
拓扑排序算法分析
拓扑排序代码实现
@(目录)
介绍
拓扑排序, 很多人都可能听说但是不了解的一种算法. 或许很多人只知道它是图论的一种排序, 至于干什么的不清楚. 又或许很多人可能还会认为它是一种啥排序. 而实质上它是对有向图的顶点排成一个线性序列.
至于定义, 百科上是这么说的:
对一个有向无环图 (Directed Acyclic Graph 简称 DAG)G 进行拓扑排序, 是将 G 中所有顶点排成一个线性序列, 使得图中任意一对顶点 u 和 v, 若边 < u,v>∈E(G), 则 u 在线性序列中出现在 v 之前. 通常, 这样的线性序列称为满足拓扑次序(Topological Order) 的序列, 简称拓扑序列. 简单的说, 由某个集合上的一个偏序得到该集合上的一个全序, 这个操作称之为拓扑排序.
为什么会有拓扑排序? 拓扑排序有何作用?
举个例子, 学习 java 系列的教程
代号 | 科目 | 学前需掌握 |
- -------- | ----- | --|
- A1 | javaSE|
- A2 | html|
- A3 | Jsp|A1,A2
- A4 | servlet|A1
- A5 | ssm|A3,A4
- A6 | springboot|A5
就比如学习 java 系类 (部分) 从 java 基础, 到 jsp/servlet, 到 ssm, 到 springboot,springcloud 等是个循序渐进且有依赖的过程. 在 jsp 学习要首先掌握 java 基础和 HTML 基础. 学习框架要掌握 jsp/servlet 和 jdbc 之类才行. 那么, 这个学习过程即构成一个拓扑序列. 当然这个序列也不唯一, 你可以对不关联的学科随意选择顺序(比如 HTML 和 java 可以随便先开始哪一个.)
那上述序列可以简单表示为:
其中五种均为可以选择的学习方案, 对课程安排可以有参考作用, 当然, 五个都是拓扑序列. 只是选择的策略不同!
一些其他注意:
DGA: 有向无环图
AOV 网: 数据在顶点 可以理解为面向对象
AOE 网: 数据在边上, 可以理解为面向过程!
而我们通俗一点的说法, 就是按照某种规则将这个图的顶点取出来, 这些顶点能够表示什么或者有什么联系.
规则:
图中每个顶点只出现一次.
A 在 B 前面, 则不存在 B 在 A 前面的路径.(
不能成环!!!!
)
顶点的顺序是保证所有指向它的下个节点在被指节点前面!(例如 A->B->C 那么 A 一定在 B 前面, B 一定在 C 前面). 所以, 这个核心规则下只要满足即可, 所以拓扑排序序列不一定唯一!
拓扑排序算法分析
正常步骤为(方法不一定唯一):
从 DGA 图中找到一个没有前驱的顶点输出.(可以遍历, 也可以用优先队列维护)
删除以这个点为起点的边.(它的指向的边删除, 为了找到下个没有前驱的顶点)
重复上述, 直到最后一个顶点被输出. 如果还有顶点未被输出, 则说明有环!
对于上图的简单序列, 可以简单描述步骤为:
1: 删除 1 或 2 输出
2: 删除 2 或 3 以及对应边
3: 删除 3 或者 4 以及对应边
3: 重复以上规则步骤
这样就完成一次拓扑排序, 得到一个拓扑序列, 但是这个序列并不唯一! 从过程中也看到有很多选择方案, 具体得到结果看你算法的设计了. 但只要满足即是拓扑排序序列.
另外观察 1 2 4 3 6 5 7 9 这个序列满足我们所说的有关系的节点指向的在前面, 被指向的在后面. 如果完全没关系那不一定前后(例如 1,2)
拓扑排序代码实现
对于拓扑排序, 如何用代码实现呢? 对于拓扑排序, 虽然在上面详细介绍了思路和流程, 也很通俗易懂. 但是实际上代码的实现还是很需要斟酌的, 如何在空间和时间上能够得到较好的平衡且取得较好的效率?
首先要考虑存储. 对于节点, 首先他有联通点这么多属性. 遇到稀疏矩阵还是用邻接表比较好. 因为一个节点的指向节点较少, 用邻接矩阵较浪费资源.
另外, 如果是 1,2,3,4,5,6 这样的序列求拓扑排序, 我们可以考虑用数组, 但是如果遇到 1,2,88,9999 类似数据, 可以考虑用 map 中转一下. 那么,
我们具体的代码思想为:
新建 node 类, 包含节点数值和它的指向(这里直接用 list 集合替代链表了)
一个数组包含 node(这里默认编号较集中). 初始化, 添加每个节点指向的时候同时被指的节点入度 + 1!(A->C)那么 C 的入度 + 1;
扫描一遍所有 node. 将所有入度为 0 的点加入一个栈(队列).
当栈 (队列) 不空的时候, 抛出其中任意一个 node(栈就是尾, 队就是头, 顺序无所谓, 上面分析了只要同时入度为零可以随便选择顺序). 将 node 输出, 并且
node 指向的所有元素入度减一
. 如果某个点的入度被减为 0, 那么就将它加入栈(队列).
重复上述操作, 直到栈为空.
这里主要是利用栈或者队列储存入度只为 0 的节点, 只需要初次扫描表将入度为 0 的放入栈 (队列) 中.
这里你或许会问为什么.
因为节点之间是有相关性的, 一个节点若想入度为零, 那么它的父节点 (指向节点) 肯定在它为 0 前入度为 0, 拆除关联箭头. 从父节点角度, 它的这次拆除联系, 可能导致被指向的入读为 0, 也可能不为 0(还有其他节点指向儿子)
至于具体 demo:
package 图论;
- import java.util.ArrayDeque;
- import java.util.ArrayList;
- import java.util.List;
- import java.util.Queue;
- import java.util.Stack;
- public class tuopu {
- static class node
- {
- int value;
- List<Integer> next;
- public node(int value) {
- this.value=value;
- next=new ArrayList<Integer>();
- }
- public void setnext(List<Integer>list) {
- this.next=list;
- }
- }
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- node []nodes=new node[9];// 储存节点
- int a[]=new int[9];// 储存入度
- List<Integer>list[]=new ArrayList[10];// 临时空间, 为了存储指向的集合
- for(int i=1;i<9;i++)
- {
- nodes[i]=new node(i);
- list[i]=new ArrayList<Integer>();
- }
- initmap(nodes,list,a);
- // 主要流程
- //Queue<node>q1=new ArrayDeque<node>();
- Stack<node>s1=new Stack<node>();
- for(int i=1;i<9;i++)
- {
- //System.out.print(nodes[i].next.size()+"55");
- //System.out.println(a[i]);
- if(a[i]==0) {s1.add(nodes[i]);}
- }
- while(!s1.isEmpty())
- {
- node n1=s1.pop();// 抛出输出
- System.out.print(n1.value+" ");
- List<Integer>next=n1.next;
- for(int i=0;i<next.size();i++)
- {
- a[next.get(i)]--;// 入度减一
- if(a[next.get(i)]==0)// 如果入度为 0
- {
- s1.add(nodes[next.get(i)]);
- }
- }
- }
- }
- private static void initmap(node[] nodes, List<Integer>[] list, int[] a) {
- list[1].add(3);
- nodes[1].setnext(list[1]);
- a[3]++;
- list[2].add(4);list[2].add(6);
- nodes[2].setnext(list[2]);
- a[4]++;a[6]++;
- list[3].add(5);
- nodes[3].setnext(list[3]);
- a[5]++;
- list[4].add(5);list[4].add(6);
- nodes[4].setnext(list[4]);
- a[5]++;a[6]++;
- list[5].add(7);
- nodes[5].setnext(list[5]);
- a[7]++;
- list[6].add(8);
- nodes[6].setnext(list[6]);
- a[8]++;
- list[7].add(8);
- nodes[7].setnext(list[7]);
- a[8]++;
- }
- }
输出结果
2 4 6 1 3 5 7 8
当然, 上面说过用栈和队列都可以! 如果使用队列就会得到 1 2 3 4 5 6 7 8 的拓扑序列
至于图的构造, 因为没有条件可能效率并不高, 算法也可能不太完美, 如有优化错误还请大佬指正!
另外, 还请各位大佬动动小手 点赞, 关注(bigsai) 一波啊! 谢谢
来源: https://www.cnblogs.com/bigsai/p/11489260.html