4.4 图的基本应用及其复杂度分析

　　习题4分析：
　　（1）先求事件的最早发生时间。
　　定义顶点V1的ve(1)=0，设T是所有以第j个顶点为头的弧的集合，<i,j>是其中的弧（活动），dut(<i,j>)是此弧的权（活动所需的时间）：
　　ve[j]=max{ve[i]+dut(<i,j>)} <i,j>∈T，j=1,2,3,…,n
　　顶点V2：
　　对V1：ve[2] = ve[1] + dut(<1,2>) = 0+6 = 6。
　　顶点V3：
　　对V1：ve[3] = ve[1] + dut(<1,3>) = 0+7 = 7。
　　顶点V4：
　　对V1：ve[4] = ve[1] + dut(<1,4>) = 0+4 = 4。
　　对V2：ve[4] = ve[2] + dut(<2,4>) = 6+23 = 29。
　　对V3：ve[4] = ve[3] + dut(<3,4>) = 7+25 = 32。
　　取其中的最大值，所以ve[4] = 32。
　　顶点V5：
　　对V2：ve[5] = ve[2] + dut(<2,5>) = 6+18 = 24。
　　对V4：ve[5] = ve[4] + dut(<2,5>) = 32+12 = 44。
　　取其中的最大值，所以ve[5] = 44。
　　顶点V6：
　　对V3：ve[6] = ve[3] + dut(<3,6>) = 7+20 = 27。
　　对V4：ve[6] = ve[4] + dut(<4,6>) = 32+15 = 47。
　　取其中的最大值，所以ve[6] = 47。
　　顶点V7：
　　对V4：ve[7] = ve[4] + dut(<4,7>) = 32+8 =40。
　　对V5：ve[7] = ve[5] + dut(<5,7>) = 44+5 = 49。
　　对V6：ve[7] = ve[6] + dut(<6,7>) = 47+10 = 57。
　　取其中的最大值，所以ve[6] = 57。
　　故完成整个工程需要57个单位时间。
　　（2）求事件的最迟开始时间。
　　定义vl[7]=ve[7]=57。
　　顶点V6：
　　对V7：vl[6] = vl[7]-dut(<6,7>) = 57-10 = 47。
　　顶点V5：
　　对V7：vl[5] = vl[7]-dut(<5,7>) = 57-5 = 52。
　　顶点V4：
　　对V7：vl[4] = vl[7]-dut(<4,7>) = 57-8 = 49。
　　对V6：vl[4] = vl[6]-dut(<4,6>) = 47-15 = 32。
　　对V5：vl[4] = vl[5]-dut(<4,5>) = 52-12 = 40。
　　取其中的最小值，故vl[4]=32。
　　顶点V3：
　　对V6：vl[3] = vl[6]-dut(<3,6>) = 47-20 = 27。
　　对V4：vl[3] = vl[4]-dut(<3,4>) = 32-25 = 7。
　　取其中的最小值，故vl[3]=7。
　　顶点V2：
　　对V5：vl[2] = vl[5-dut(<2,5>) = 52-18 = 33。
　　对V4：vl[2] = vl[4]-dut(<2,4>) = 32-23 = 9。
　　取其中的最小值，故vl[2]=9。
　　顶点V1：
　　对V4：vl[1] = vl[4-dut(<1,4>) = 32-4 = 28。
　　对V3：vl[1] = vl[3]-dut(<1,3>) = 7-7 = 0。
　　对V2：vl[1] = vl[2]-dut(<1,2>) = 9-6 = 3。
　　取其中的最小值，故vl[1]=0。
　　（3）对比关键路径。
　　所有事件的最早发生时间ve={0,6,7,32,44,47,57}
　　所有事件的最迟开始时间vl={0,9,7,32,52,47,57}
　　所以，关键路径为：(V1,V3,V4,V6,V7)
　　（4）求活动的最早发生时间和最迟开始时间。
　　求解过程如表4-9所示。
 

表4-9  求活动的最早发生时间和最迟开始时间

　　所以关键活动为：(<1,3>，<3,4>，<4,6>，<6,7>)。
　　习题5分析：
　　本题的算法思想是：利用深度优先遍历进行搜索，用栈保存遍历路径上的节点，并用dist记下当前的路径长度。从v=vi出发，找v的邻接点w，若w已经被访问过，则找下一个邻接顶点；若w=vj，且dist=len-1，则该路径即为所求的路径。若w！=wj，且dist<len-1，则从w出发继续遍历，找下一个邻接顶点；若找不到下一个邻接顶点（设w=0），则退栈，找前一个顶点的下一个邻接顶点，若栈空，则说明不存在这样的路径。

　　#define  max   100
　　void  path(AdjList adj, int vi ,int vj, int len)
　　{
　　  int  v,w,top=0,dist=0,head;
　　  int  stack[max],visited[max];           //定义栈和标志数组
　　  struct  vnode *p;
　　  v=vi; visited[v]=1;
　　  head=1                                           //head在邻接表头第一次取邻接顶点时为1，否则为0；
　　  do                                                   //w为v在图中的邻接点，若邻接点已经查遍，则w=0
　　  {
　　    if (head!=0) p=adj[v]->firstarc;
　　    else
　　    {
　　      head=0; p=p->next;
　　    }
　　    if(p=NULL) w=0;
　　    else
　　      w=p->adjvex;
　　    if(w!=0)
　　      if(visited[w]==0)                             //顶点v未被访问过
　　       if(w=vj&&dist==len-1)
　　        {
　　          dist++ ; top++; stack[top]=v; 
　　        }
　　     if(w!=vj&&dist<len-1)
　　     {
　　       dist++; top++; stack[top]=v; visited[w]=1; v=w; head=1
　　     }
　　     else
　　       if(top>0)
　　        {
　　           visited[v]=0; v=stack[top]; head=1; top--; dist--;
　　        }
　　    }while ((top!=0||w==0)&&(dist!=len));
　　if(top>0)
　　for(i=1; i<=top ;i++)
　　  printf("%d"，stack[i]);
　　   else
　　     printf("没有这样的路径！\n");
　　}