数据结构（十）——拓扑排序和关键路径

文章目录

• 1. 拓扑排序
• 2. 逆拓扑排序
• 3. 关键路径

1. 拓扑排序

（1）定义

• AOV网络：节点代表活动，在这种关系下通过有向边连接的节点对（Vi, Vj）表明Vi必须在Vj之前执行。
  ①AOV网络一定构成一个有向无环图结构。
  ②对于任意节点Vi来说，在其邻接列表中不可能包含自身。

• 拓扑排序：一种对有向无环图（DAG）中的顶点进行排列的方式，在这种排列中任何一条从顶点A指向顶点B的路径都意味着在排列顺序中B位于A之后。
  ①可视为描述工程事件间顺序关系的一种数学模型。
  ②可能存在多个不同的拓扑序列。

（2）思路
初始化时将AOV网中所有入度为0的顶点加入栈中。

从栈结构中取出一个入度为零的节点并输出之。
将该节点及其所有出边一并移除。
重复执行上述步骤直至AOV网络为空或当前网络不再存在无前驱节点。

![在这里插入图片描述](https://ad.itadn.com/c/weblog/blog-img/images/2025-05-31/dENRxoVIG15h6FT