7.5 有无环图及应用.pptVIP

7.5 有向无环图及应用 7.5.1 拓扑排序 ——用顶点边表示活动的网络，简称 AOV网络 (Activity On Vertices) 顶点：一个工程中的活动(Activity) 边：活动的顶点间的优先关系(Relation) 要解决的问题是： 将各个顶点 （代表各个活动）排列成一个线性有序 的序列，使得AOV网络中所有应存在的前驱和后继关系 都能得到满足。 可以用有向图表示一个工程。在这种有向图中，用顶点表示活动。有向边Vi, Vj表示：Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活动的AOV网络(Activity On Vertices)。 在AOV网络中，如果活动Vi 必须在活动Vj 之前进行，则存在有向边Vi, Vj， AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。 因此，对给定的AOV网络，必须先判断它是否存在有向环。 一、什么是拓扑排序 将各个顶点 (代表各个活动)排列成一个线性有序的 序列，使得AOV网络中所有应存在的前驱和后继关系都 能得到满足。 这种构造AOV网络全部顶点的拓扑有序序列的运算 就叫做拓扑排序。 例如，对学生选课工程图进行拓扑排序，得到的拓 扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9, C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 例如，对学生选课工程图进行拓扑排序，得到的拓 扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 二、进行拓扑排序的方法 首先建立（ n 个顶点的）AOV网。 （1） 在AOV网络中选一个没有直接前驱的顶点（入度 为0的顶点）, 并输出之; （2）从图中删去该顶点, 同时删去所有它发出的边； 重复（1）和（2）， 直到全部顶点均已输出， 拓扑有序序列形成，拓扑排序完成； 若图中还有未输出的顶点，但已跳出处理循环。这 说明图中存在环。 在邻接表的头结点中增设了一个数据项id，记录该顶点的入度。 入度为零的顶点即无前驱的顶点。 在拓扑排序算法中，使用一个存放入度为零的顶点的链式栈，供选择和输出无前驱的顶点。只要出现入度为零的顶点，就将它加入栈中。 五、拓扑排序算法思想： (1) 建立入度为零的顶点栈; (2) 当入度为零的顶点栈不空时, 重复执行： (2)-1 从顶点栈中退出一个顶点, 并输出之; (2)-2 从AOV网络中删去这个顶点和它发出的 边, 边的终顶点入度减一; (2)-3 如果边的终顶点入度减至0, 则该顶点进 入度为零的顶点栈; (3) 如果输出顶点个数少于AOV网络的顶点个 数, 则报告网络中存在有向环。 将顶点 i进栈时，执行以下指针的修改： dig[i].id = top; top = i; // top指向新栈顶i, 原栈顶元素放在id[i]中 退栈操作可以写成： j = top; top = dig[top].id; //位于栈顶的顶点的位置记于 j, top退到次栈顶 7.5.2 关键路径 ——用边表示活动的网络，简称 AOE网络 (Activity On Edges) 边：一个工程中的活动(Activity) 边上权值：活动持续时间(Duration) 顶点：事件 (Event) 要解决的问题是： (1) 完成整个工程至少需要多少时间(假设网络中没有环)? (2)为缩短完成工程所需的时间, 应当加快哪些活动? 完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。 定义几个与计算关键活动有关的量： （1）事件Vj 的最早可能开始时间Ve(j)