数据结构第6章 图4.ppt

第六章 图 图的概念 图的存储结构 图的遍历方法 求生成树 找最短路径 关键路径 拓扑排序 计算机科学与工程学院《数据结构》课程组 * 关键路径问题的提出 把工程计划表示为有向图，顶点表示事件，弧表示活动 每个事件表示在它之前的活动已完成，在它之后的活动可以开始 设一个工程有11项活动，9个事件 事件 V1 表示整个工程开始 事件V9 表示整个工程结束 问题 完成整项工程至少需要多少时间？ 哪些活动是影响工程进度的关键？ 9 8 7 6 4 5 3 2 1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 * AOE网：以顶点表示事件，弧代表活动，权表示活动需要的时间。顶点所代表的事件实际上就是表示以它为弧头的所有弧表示的活动已完成，所有以它为弧尾的弧代表的活动可以开始这一种状态。 源点和汇点：在正常情况(无环)下，网中只有一个入度为零的点称为源点，一个出度为零的点称为汇点。 关键路径：完成整个工程的最短时间是从源点到汇点的最长路径的长度(路径长度等于路径上各边的权之和，而不是路径上弧的数目)。这条具有最大长度的路径称为关键路径 关键路径问题的有关术语 * 如：(v1，v3，v5，v7，v9) 就是一条长度为18的关键路径 图6.25 一个AOE-网 关键路径问题的有关术语举例 * 路径长度 路径上各活动持续时间之和 关键路径 路径长度最长的路径叫~ ee(i) 表示事件Vi的最早发生时间 le(i) 表示事件Vi的最迟发生时间 关键路径问题的有关术语 e(k) 表示活动ak=vi，vj的最早开始时间 l(k) 表示活动ak=vi，vj的最迟开始时间 l(k)-e(k) 表示完成活动ak的时间余量 关键活动 关键路径上的活动，即l(i)=e(i)的活动 * 设ak=vi，vj上的权w(k)=w(i，j) 从ee(1)=0开始向前递推求ee(j)： ee(j)=max{ee(i)+w(i，j)} 2≤j≤n vi，vj∈T，其中T是所有以Vj为头的弧的集合。 从le(n)=ee(n)开始向后递推求le(i) le(i)=min{le(j)—w(i，j)} 1≤i≤n-1 vi，vj∈S，其中S是所有以vi为尾的弧的集合 对于每条边ak=vi，vj求e(k)和l(k)： e(k)=ee(i), l(k)=le(j), 1≤k≤m，m为图中的边数 计算l(k)-e(k) 若l(k)-e(k)=w(k)， 则ak是关键活动。 i j ak 求关键路径步骤 * 求关键路径步骤 求ee(i) 求le(j) 求e(i) 求l(i) 计算l(i)-e(i) 9 8 7 6 4 5 3 2 1 a2=4 a3=5 a5=1 a6=2 a9=4 a1=6 a4=1 a7=9 a8=7 a10=2 a11=4 V1 V2 V3 V4 V5 V6 V7 V8 V9 顶点 ee le 0 6 4 5 7 7 16 14 18 0 6 6 8 7 10 16 14 18 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 活动 e l l-e ? ? ? ? ? ? 0 0 0 0 2 2 6 6 0 4 6 2 5 8 3 7 7 0 7 7 0 7 10 3 16 16 0 14 14 0 0 3 3 注意:以后采用: l(k)=le(j)- w(k),则若l(k)-e(k)=0， 则ak是关键活动 * 求ee的顺序应该是按拓扑有序的次序； 求le的顺序应该是按拓扑逆序的次序； 在拓扑排序的过程中,另设一个“栈”记下拓扑有序序列. 求关键路径的实现要点 * 以邻接表作存储结构 从源点V1出发，令ee[1]=0,按拓扑序列求各顶点的ee[i] 从汇点Vn出发，令le[n]=ee[n],按逆拓扑序列求其余各顶点的le[i] 根据各顶点的ee和le值，计算每条弧的e[i]和l[i],找出e[i]=l[i]的关键活动 邻接表结点： typedef struct node { int vex; //顶点域 int length; //权值 struct node *next; //链域 }JD; 表头结点： typedef struct tnode { int vexdata; int in; //入度域 struct node *link; //链域 }TD; TD g[M]; //g[0]不用 求关键路径的算法实现 * 输入顶点和弧信息，建