数据结构-拓扑排序_数据结构中拓扑排序

作者：菜鸟追梦旅行 | 2024-06-04 01:56:00

踩

数据结构中拓扑排序

1。AOV网

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网。（Activity On Vertex Network）。

2.拓扑排序

设G=（V,E）是一个具有n个顶点的有向图，V中的顶点序列v1,v2,。。。，vn，满足若从顶点Vi到vj有一条途径，则在顶点序列中顶点vi必在顶点vj之前。则我们称这样的顶点序列为一个拓扑排序。所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

3.拓扑排序算法

从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或AOV网中不存在入度不为0的顶点为止。

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