计算机考研知识点解析：数据结构之拓朴排序与关键路径

对 AOV 网进行拓扑排序的基本思路是:从 AOV 网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV 网中不存在入度为0的顶点为止。为什么选择一个入度为0的顶点输出呢?因为拓扑排序是表示的是一种先后关系，入度为零0的点表示没有前驱了。算法思想实现步骤

(1)在AOV网中选择一个没有前驱的顶点且输出;

(2)在AOV网中删除该顶点以及从该顶点出发的(以该顶点为尾的弧)所有有向弧(边) ;

(3)重复(1)、(2)，直到图中全部顶点都已输出(图中无环)或图中不存在无前驱的顶点(图中必有环)。

拓扑排序的唯一性讨论：拓扑序列往往是不唯一的，且有两种情形会导致拓扑序列不唯一。如图(a)所示，存在一个入度为0的点，但是存在顶点1和顶点2，顶点4和顶点5平行(他们之间无前驱或者后继的关系)的情况，此时顶点1和顶点2，顶点4和定点5的先后顺序在拓扑序列中是不确定的。

如图(b)所示，存在多个入度为0的点，也就是顶点1和顶点2的入度为0，那么他们之间的先后关系也是不确定的。

带权有向图以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，称为AOE网。AOE网中从源点到汇点的最大路径长度的路径称为关键路径，关键路径长度是整个工程所需的最短工期。关键路径上的活动称为关键活动。

关键路径的性质：

(1)可以通过加快关键活动，来缩短整个工程的工期。并非关键活动缩短多少工期就缩短多少，因为缩短到一定的程度，该关键活动可能变成非关键活动了。

(2)关键路径并不唯一。对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。