2022考研计算机数据结构：拓扑排序

2022考研计算机数据结构：拓扑排序

　

　　拓扑排序

　　拓扑排序：将有向图中的顶点排成一个拓扑序列的过程。

　　拓扑序列：有向图中的一个顶点序列，对图中任意两个顶点i和j，若i是j的前驱结点，则在线性序列中i先于j。

　　AOV网：以顶点表示活动，有向边表示活动之间的领先关系的有向图。

　　注意：拓扑序列不是唯一的!

　　可以用拓扑排序的方法来测试有向图是否存在回路，若经过拓扑排序后所有顶点都已列出，则不存在回路。

　　排序步骤：

　　a.任选一个入度为零的顶点，并输出之;

　　b.从图中删除该顶点及其所有出边;

　　c.重复步骤1、2，直到所有顶点都已输出，或者直到剩下的图中再也没有入度为零的顶点为止，后者表示图中包含有向回路。

　　第五单元 第六单元 第七单元

　　以上是小编为大家整理分享的“2022考研计算机数据结构：拓扑排序”相关内容，希望对大家有帮助。祝大家考上理想的院校!

2022考研计算机数据结构：拓扑排序