一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。
例如，汽车装配工程可分解为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上
漆，装刹车，装门等等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。
任务的先后顺序可用有向图表示——称为顶点活动（ Activity On Vertex, AOV）网络。有向
图的顶点代表任务，有向边(i, j) 表示先后关系：任务 j 开始前任务 i 必须完成。图 1 - 4 显
示了六个任务的工程，边（ 1 , 4）表示任务 1 在任务 4 开始前完成，同样边（ 4 , 6）表示
任务 4 在任务 6 开始前完成，边（1 , 4）与（4 , 6）合起来可知任务 1 在任务 6 开始前完成，
即前后关系是传递的。由此可知，边（1 , 4）是多余的，因为边（1 , 3）和（3 , 4）已暗示
了这种关系。
在很多条件下，任务的执行是连续进行的，例如汽车装配问题或平时购买的标有“需要
装配”的消费品（自行车、小孩的秋千装置，割草机等等）。我们可根据所建议的顺序来装
配。在由任务建立的有向图中，边（ i, j）表示在装配序列中任务 i 在任务 j 的前面，具有
这种性质的序列称为拓扑序列（topological orders 或 topological sequences)。根据任务的有向
图建立拓扑序列的过程称为拓扑排序（topological sorting）。图 1 - 4 的任务有向图有多种拓
扑序列，其中的三种为 1 2 3 4 5 6，1 3 2 4 5 6 和 2 1 5 3 4 6，序列 1 4 2 3 5 6 就不是拓扑序
列，因为在这个序列中任务 4 在 3 的前面，而任务有向图中的边为（ 3 , 4），这种序列与
边（ 3 , 4）及其他边所指示的序列相矛盾。可用贪婪算法来建立拓扑序列。算法按从左到
右的步骤构造拓扑序列，每一步在排好的序列中加入一个顶点。利用如下贪婪准则来选择顶
点：从剩下的顶点中，选择顶点 w，使得 w 不存在这样的入边（ v,w），其中顶点 v 不在
已排好的序列结构中出现。注意到如果加入的顶点 w 违背了这个准则（即有向图中存在边
（ v,w）且 v 不在已构造的序列中），则无法完成拓扑排序，因为顶点 v 必须跟随在顶点 w
之后。贪婪算法的伪代码如图 1 3 - 5 所示。while 循环的每次迭代代表贪婪算法的一个步骤。
现在用贪婪算法来求解图 1 - 4 的有向图。首先从一个空序列 V 开始，第一步选择 V 的
第一个顶点。此时，在有向图中有两个候选顶点 1 和 2，若选择顶点 2，则序列 V = 2，第一
