数据结构（C语言版）（第2版）.pptVIP

这种带入度的邻接表存储结构定义如下：#defineM20typedefcharvertextype;typedefstructnode{ /*边结点类型定义*/intadjvex;structnode*next;}edgenode;typedefstructde/*带顶点入度的头结点定义*/{edgenode*FirstEdge;vertextypevertex;intid;/*顶点的入度域*/}vertexnode;typedefstruct{ /*AOV网络的邻接表结构*/vertexnodeadjlist[M];intn,e;}AovGraph;基于这种存储结构，拓扑排序算法可描述为算法8.9。/******************************************//*拓扑排序算法文件名:topsort.c*//******************************************/inttopsort(AovGraphg) /*函数返回输出的顶点的个数*/{intk=0,i,j,v,flag[M];intqueue[M]; /*队列*/inth=0,t=0;edgenode*p;for(i=0;ig.n;i++) flag[i]=0; /*访问标记初始化*/for(i=0;ig.n;i++) /*先将所有入度为0的结点进队*/if(g.adjlist[i].id==0flag[i]==0){queue[++t]=i; flag[i]=1;}printf(\nAOV网的拓扑序列是：\n);while(ht) /*当队列不空时*/{v=queue[++h]; /*队首元出队*/printf(%c,g.adjlist[v].vertex);k++; /*计数器加1*/p=g.adjlist[v].FirstEdge;while(p) /*将所有与v邻接的顶点的入度减1*/{j=p-adjvex; if(--g.adjlist[j].id==0flag[j]==0) /*若入度为0则将进队*/ {queue[++t]=j;flag[j]=1;} p=p-next; }}returnk;}算法8.9拓扑排序程序运行结果:8.8关键路径如果在无有向环的带权有向图中用有向边表示一个工程中的活动(Activity)用边上权值表示活动持续时间(Duration)用顶点表示事件(Event)则这样的有向图叫做用边表示活动的网络，简称AOE(ActivityOnEdges)网络。AOE网络在某些工程估算方面非常有用。例如，可以使人们了解：(1)完成整个工程至少需要多少时间(假设网络中没有环)?(2)为缩短完成工程所需的时间,应当加快哪些活动? 在AOE网络中,有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(CriticalPath)。要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径.例如，下图就是一个AOE网。V3V1a4=3a1=3a2=2a6=3a5=4a3=2a7=2a8=1顶点表示事件边表示活动事件Vj发生表示ak已结束akVjVi事件Vi发生表示ak可以开始AOE网V2V4V5V6Dijkstra算法中各辅助数组的变化ABDCFE24152881810134Dijkstra算法数组的变化结果