|
知识路径: > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 图的相关算法 > 拓扑排序 >
|
相关知识点:2个
|
|
|
|
拓扑排序是将AOV网中所有顶点排成一个线性序列的过程,并且该序列满足:若在AOV网中从顶点νi到νj有一条路径,则在该线性序列中,顶点νi必然在顶点νj之前。
|
|
|
一般情况下,假设AOV网代表一个工程计划,则AOV网的一个拓扑排序就是一个工程顺利完成的可行方案。对AOV网进行拓扑排序的方法如下:
|
|
|
(1)在AOV网中选择一个入度为零(没有前驱)的顶点且输出它;
|
|
|
|
(3)重复上述两步,直至网中不存在入度为零的顶点为止。
|
|
|
按照上述步骤进行拓扑排序的过程如下图所示,得到的拓扑序列为6,1,4,3,2,5。显然,对有向图进行拓扑排序所产生的拓扑序列有可能是多种。
|
|
|
|
|
执行的结果会有两种情况:一种是所有顶点已输出,此时整个拓扑排序完成,说明网中不存在回路;另一种是尚有未输出的顶点,剩余的顶点均有前驱顶点,表明网中存在回路,拓扑排序无法进行下去。
|
|
|