5.7 拓扑排序★3◎3

5.7 拓扑排序★3◎3

　　一个无环的有向图称为“有向无环图”（Directed Acyclic Graph），简称DAG图。对DAG图进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v>∈E(G)，则u在线性序列中出现在v之前。通俗地说，原图中可能存在某些顶点无法比较先后顺序，而拓扑排序后，任何一对顶点都将存在一个先后次序。
　　1．AOV-网
　　有向无环图常常用来描述一些前后相关的事件，把顶点当成活动，用弧表示不同活动之间的相关性，弧<i，j>表示必须先完成事件i，才可以进行事件j，这样的有向图称为“顶点表示活动的网”（Activity On Vertex Network），简称AOV-网。比如，某书作者以书本的各章节学习为顶点，各章节学习的先后顺序作为边，构成一个有向图，就是AOV-图，如图5-13所示。

　　在AOV-网中，如果存在一条从顶点i到顶点j的有向路径，则称i是j的“前驱”，j是i的“后继”；如果网中存在弧<i，j>，则称i是j的“直接前驱”，j是i的“直接后继”。
　　引入符号“≤”代表顶点间的先后关系，比如“V0≤V2”代表V0领先于V2，V0是V2的前驱，V2是V0的后继。
　　当且仅当AOV-网中不存在环时，才可以对其进行拓扑排序，拓扑排序得到的有序序列并不唯一，如图5-13中的两个拓扑排序序列如下：
　　（V0，V1，V3，V2，V4，V5）或者（V0，V1，V2，V3，V4，V5）
　　2．拓扑排序算法
　　可按照如下步骤对DAG图进行拓扑排序：
　　①在图G中任意选择一个入度为0的顶点，如果没有就说明拓扑排序完成。
　　②将该顶点输出到拓扑排序序列。
　　③在图G中删除此顶点及以该顶点为弧尾的弧。
　　④回到第①步继续执行。
　　如图5-14所示就是以上算法的一个实例，它产生的拓扑序列为（V0，V1，V3，V2，V4，V5）。
　　当使用邻接表表示图时，拓扑排序算法时间复杂度为O(e+n)。