数据结构—拓扑排序_数据结构中的沱湖排序

作者：知新_RL | 2024-06-04 02:01:39

踩

数据结构中的沱湖排序

问：什么是拓扑排序，有什么用，应用场景是什么？

首先搞清楚什么是AOV网，如果用DAG(有向无环图)来表示一个工程，用<Vi,Vj>来表示活动Vi必须先于Vj进行的这样一种关系，我们把这种有向图称为顶点表示活动的网络，记作AOV网。

拓扑排序：有一个有向无环图的顶点组成的一个序列，必须满足如下条件：

①每个顶点都必须出现，且只能出现一次；

②如果顶点A在序列中的位置处在B的前面，那么在图中不存在由B到A的路径。

注意拓扑排序序列并不唯一，每个AOV网都可以有一个或者多个拓扑序列。

关于应用场景，凡是没有环，即没有回路的工程图或者流程图都可以应用到，序列体现出活动之间的优先关系。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/669929