数据结构PPT教学课件-第7章 图.ppt

第7章 图 7.2 图的存储结构 7.3 图的遍历和求图的连通分量 7.4 图 的 生 成 树 7.5 最短路径 7.6 有向无环图及应用 7.7 图的算法C语言程序实现举例 case 2: n=creat1(dig2);break; case 3: toposort(dig2, n);break; case 4: criticalpath(dig, n);break; } } }/*main end int creat(vexnodel dig［］) /*建立AOE邻接链表*/ ? { int i, j, a, b, c; edgenodel *p, *q; printf(input vex number:); scanf(%d, i); /*输入AOE图的顶点数*/ (3) 求每一项活动ai(1≤i≤m)的最早开始时间e(i)=ve(j), 最晚开始时间l(i)=vl(k)-dut(〈j, k〉)。若某条弧满足e(i)=l(i), 则它是关键活动。  对于图7.19所示的AOE网, 按以上步骤的计算结果见表7.3, 可得到a1, a4, a7, a8, a10, a11是关键活动。 求出AOE网中所有关键活动后, 只要删去AOE网中所有的非关键活动, 即可得到AOE网的关键路径。这时从开始顶点到达完成顶点的所有路径都是关键路径。一个AOE网的关键路径可以不止一条, 如图7.19的AOE网中有两条关键路径, 即(v1, v2, v5, v7, v9)和(v1, v2, v5, v8, vg), 它们的路径长度都是16。如图7.22所示。下面给出的求关键活动的算法也就是求关键路径的算 图 7.22 图7.19所示AOE网的关键路径 下面给出的求关键活动的算法也就是求关键路径的算法。  为了便于第2步求值, 需在第1步拓朴排序时保存拓扑序列。 在7.6.1节的拓朴排序算法中,TOPOSORT是利用栈来保存入度为零的顶点, 排序结束后, 栈没有保存拓朴序列。因此, 我们必须对TOPOSORT算法做如下修改: 用顺序队列tpord［n］保存入度为零的顶点, 将原算法中的有关栈操作改为相应的队列操作。 在排序过程中, 当删去以vj为起点的出边〈vj, vk 〉时, 可根据vj的ve(j)值, 用递推公式(7.1)对vk的ve(k)值进行修改。为此, 必须在排序前将各顶点的ve值均置上初值零。 若ve(k)值已对vk的所有前趋顶点vj修改过, 则ve(k)值就是最终求得的vk的最早发生时间。一旦排序结束, tpord［n］中就保存了拓朴序列。 具体算法如下:  算法 7.10 typedef stuct node1 { int adjvex; /*邻接点域 */ int dut; /*权值 */ struct node1 next; /链域 */ } edgenode1; /*边表结点 */  typedef struct { vextype vertex; /*顶点信息 */ int id; /*入度 * edgenode1 link; /*边表头指针 */ } vexnode1; /*顶点表结点 */ vexnode1 dig1［n］; /*全程量邻接链表 */ void criticalpath(vexnode1 dig［ ］) /*dig是AOE网的带权邻接链表*/ { int front=-1; rear=-1; /*顺序队列的首尾指针置初值为-1*/ int tpord［n］, vl［n］, ve［n］; int l［maxsize］, e［maxsize］; edgenode1 p; for (i=0; in; i++) ve［i］=0; /*各事件vi+1的最早发生时间置初值零 */ for (i=0; in; i++) /*扫描顶点表, 将入度为零的顶点入队 */ if (dig［i］.id==0) tpord［++rear］=i; m=0; /*计数器初始化 */ while (front![KG-*2]=rear)