您好,登录后才能下订单哦!
这篇文章主要介绍了Java如何实现拓扑排序算法,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
百科上这么定义的:
对一个有向无环图(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以及对应边
4:重复以上规则步骤
这样就完成一次拓扑排序,得到一个拓扑序列,但是这个序列并不唯一!从过程中也看到有很多选择方案
,具体得到结果看你算法的设计了。但只要满足即是拓扑排序序列。
另外观察 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
的拓扑序列
感谢你能够认真阅读完这篇文章,希望小编分享的“Java如何实现拓扑排序算法”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。