摩杰登录
- 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。
- 简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
- 在一个有向图中,对所有的节点进行排序,要求没有一个节点指向它前面的节点。
- 先统计所有节点的入度,对于入度为0的节点就可以分离出来,然后把这个节点指向的节点的入度减一。
- 一直做改操作,直到所有的节点都被分离出来。
- 如果最后不存在入度为0的节点,但还存在节点,那就说明有环,不存在拓扑排序,也就是很多题目的无解的情况。
- 先把入度为0 的节点找到并打印
- 删掉入度为0的节点,继续循环1的步骤,直至图为null。
是遍历整个图中的顶点,找出入度为0的顶点,然后标记删除该顶点,更新相关顶点的入度,由于图中有V个顶点,每次找出入度为0的顶点后会更新相关顶点的入度,因此下一次又要重新扫描图中所有的顶点。故时间复杂度为O(V^2)
问题:由于删除入度为0的顶点时,只会更新与它邻接的顶点的入度,即只会影响与之邻接的顶点。但是上面的方式却遍历了图中所有的顶点的入度。
先将入度为0的顶点放在栈或者队列中。当队列不空时,删除一个顶点v,然后更新与顶点v邻接的顶点的入度。只要有一个顶点的入度降为0,则将之入队列。此时,拓扑排序就是顶点出队的顺序。该算法的时间复杂度为O(V+E)
该算法借助队列来实现时,感觉与 二叉树的 层序遍历算法很相似啊。说明这里面有广度优先的思想。
第一步:遍历图中所有的顶点,将入度为0的顶点 入队列。
第二步:从队列中出一个顶点,打印顶点,更新该顶点的邻接点的入度(减1),如果邻接点的入度减1之后变成了0,则将该邻接点入队列。
第三步:一直执行上面 第二步,直到队列为空。
第7行for循环:先将图中所有入度为0的顶点入队列。
第11行while循环:将入度为0的顶点出队列,并更新与之邻接的顶点的入度,若邻接顶点的入度降为0,则入队列(第16行if语句)。
第19行if语句判断图中是否有环。因为,只有在每个顶点出队时,count++。对于组成环的顶点,是不可能入队列的,因为组成环的顶点的入度不可能为0(第16行if语句不会成立).
因此,如果有环,count的值 一定小于图中顶点的个数。
DirectedGraph.java中定义了图 数据结构,(图的实现可参考:数据结构--图 的JAVA实现(上))。并根据FileUtil.java中得到的字符串构造图。
构造 图之后,topoSort方法实现了拓扑排序。
FileUtil.java负责从文件中读取图的信息。将文件内容转换成 第一点 中描述的字符串格式。--该类来源于网络
测试类:TestTopoSort.java
以上内容为参照多个大佬的博客整合后的内容,主要代码部分为?https://www.cnblogs.com/hapjin/p/5432996.html
其余纯手打,有错误请指出,感谢