数据结构第七章讲课.ppt

* 算法描述 输入顶点和弧信息，建立其邻接表 计算每个顶点的入度 对其进行拓扑排序 排序过程中求顶点的Ve[i] 将得到的拓扑序列进栈 按逆拓扑序列求顶点的Vl[i] 计算每条弧的e[i]和l[i],找出e[i]==l[i]的关键活动 * 计算各顶点的Ve值在拓扑排序的过程中进行，需对拓扑排序的算法作如下修改： (a)在拓扑排序之前设初值，令ve[i]=0(1≤i≤n)。 (b)在拓扑排序的算法中增加一个计算Vj的直接后继Vk的最早发生时间的操作： 若 ve[j]+weight(j, k) ve[k] 则 ve[j]+weight(j, k) ? ve[k] (c)为计算各顶点的vl值，需记下逆拓扑有序序列可在拓扑排序算法中，增设一个栈S1记录拓扑有序序列。 两个数组：TimeType ve[n]，vl[n] ； * a b c d e f g h k 6 4 5 2 1 1 8 7 2 4 4 0 0 0 0 0 0 0 0 0 6 4 5 7 7 15 14 17 18 18 18 18 18 18 18 18 18 16 14 7 6 6 10 8 3 拓扑序列为: a-b-c-e-g-d-f-h-k 18 2 0 0 1 2 3 4 5 6 7 8 a 3 5 2 4 1 6 ^ b 4 1 ^ c 4 1 ^ d 5 2 ^ e 7 7 6 8 ^ f 7 4 ^ g 8 2 ^ h 8 4 ^ k ^ a b c d e f g h k ve vl * void critical_path(AdjGraph g){ //为求ve[i]，用栈s1存放入度为0的顶点序号； // 为求vl[i]，用栈s2存放拓扑序列的顶点序号； ve[0..g.vexnum-1]=0；initstack(s1)；initstack(s2)； for(i=0；ig.vexnum；i++) if(g.adjlist[i].id==0)push(s1,i); //入度为0的顶点序号入栈 while (! empty(s1) ) { j=pop(s1)； //取拓扑序列顶点序号 push(s2，j)；//存拓扑序列顶点序号 p=g.adjlist[j].link； while (p≠NULL) { k= p→adjvex；g.adjlist[k].id--； if (g.adjlist[k].id ==0) push(s1，k)； * if (ve[j]+p→weightve[k]) ve[k]=ve[j]+p→weight ; p = p→nextarc；} //end_while (p≠NULL) } //end_while(!emptp(s1))，求Ve[j]完成。 vl[0.. g.vexnum-1]=ve[g.vexnum-1]；//初始化l[i]=vl[n] while(! empty(s2)）// 按逆拓扑序列求各顶点的vl值 { j=pop(s2)； p=g.adjlist[j].link； while( p≠NULL){ k= p→adjvex； if(vl[k]-p→weight )vl[j]) vl[j]=vl[k]-p→weight ); p = p→nextarc； } //end_while (p≠NULL) }；//end_while(! empty(s2))，求Vl[j]完成。 * for(j=0；jg.vexnum；j++){//已知ve[i]、vl[i],求e和l p=g.adjlist[j].link； while( p≠NULL){ k= p→adjvex； e=ve[j]；l=vl[k]- p→weight ； if(e= =l) tag=‘√’； else tag=‘ ‘；//标志关键活动 printf(j，k， p→weight ，e，l，tag) ； p = p→nextarc；} //end_while }