基本概念
有向无环图(DAG)：图中某一顶点可能有多个前驱但不存在回路
AOV网：用顶点表示活动，用弧表示活动之间的制约关系（用以解决拓扑排序）
拓扑排序：在AOV网中没有回路的前提下，将全部活动排成一个线性序列，若AOV网中有弧<i，j>存在，则在序列里i一定在j前面，具有这种性质的线性序列叫拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序
一、拓扑排序的方法
1、在有向图中选一个没有前驱的顶点输出
2、删除图中该顶点和所有以它为尾的弧
3、重复以上两步，直至输出全部顶点或图中不存在无前驱的顶点
由此得到一个拓扑序列，一个AOV网的拓扑序列不是唯一的。
二、拓扑排序的应用
检测AOV网中是否存在环：
对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环
最后
以上就是慈祥楼房最近收集整理的关于数据结构学习——图的拓扑排序基本概念一、拓扑排序的方法二、拓扑排序的应用的全部内容，更多相关数据结构学习——图内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复