《数据结构第七章图严蔚敏精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据结构第七章图严蔚敏精品文稿.ppt（134页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构第七章图严蔚敏第1页，本讲稿共134页第六章 图第六章 图知 识 点图的逻辑结构特征及图的基本术语邻接矩阵和邻接表两种图的存储结构的特点及适用范围深度优先搜索和广度优先搜索两种遍历算法的特点和执行过程生成树和最小生成树的概念及构造最小生成树的prim和kruskal算法最短路径的含义及求最短路径的算法拓扑排序的基本思想和步骤关键路径法及其在管理科学中的作用第2页，本讲稿共134页第六章 图难 点图的遍历、最小生成树、最短路径、拓朴排序算法的理解关键路径法求关键活动和关键路径的方法要 求 熟练掌握以下内容：图的存储结构图的遍历算法 了解以下内容：图的最小生成树和求最小生成树算法的基本思想
2、带权有向图的最短路径问题利用AOV网络的拓朴排序问题利用AOE网络的关键路径法第3页，本讲稿共134页第六章 图第六章目录7.1 图的定义和基本术语7.2 图的存储方式7.3 图的遍历7.4 最小生成树7.5 最短路径7.6 拓扑排序7.7 关键路径法7.8 应用实例与分析小 结习题与练习第4页，本讲稿共134页第六章 图7.1 图的定义和基本术语图：图G由V（G）和E（G）这两个集合所组成，记为G=（V，E），其中V（G）是顶点（Vertex）的非空集，每个顶点可以标以不同的字符或数字；E（G）是边（Edge）的集合，特殊情况下E（G）可以是空集。每个边由其所连接的两个顶点表示。无向图：对于
3、一个图G，若边集合E（G）为无向边的集合，则称该图为无向图。有向图：对于一个图G，若边集合E（G）为有向边的集合，则称该图为有向图。第5页，本讲稿共134页第六章 图图7.1 有向图与无向图无向图G1有向图有向图G2第6页，本讲稿共134页第六章 图完全图：在一个有n个顶点的无向图中，若每个顶点到其它（n-1）个顶点都连有一条边，则图中共有n(n-1)/2条边，这种图称为完全图（Complete graph，也称完备图）。左图所示就是左图所示就是n=4的完全图，它一的完全图，它一共有六条边。共有六条边。第7页，本讲稿共134页第六章 图权和网络：有些图，对应每条边有一相应的数值，这个数值叫做该
4、边的权(Weight)。边上带权的图称为带权图，也称为网络(Network)。子图：设有两个图G=(V,E)和G=(V,E)，若V(G)是V(G)的子集，且E(G)是E(G)的子集，则称G是G的子图(Subgraph)。例如图7.3所示的图是图7.1中G1的一些子图。第8页，本讲稿共134页第六章 图图7.3 子图第9页，本讲稿共134页第六章 图顶点的度：图中与每个顶点相连的边数，叫该顶点的度(Degree)。例如图7.1的图G1中，顶点的度数为2，顶点的度数为3，。入度、出度：对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于
5、其入度和出度之和。例如在图7.1的图G2中，顶点的入度为1，出度为2，而顶点的入度为1，出度为0，因为有一条边指向它，而没有边从它指出去。第10页，本讲稿共134页第六章 图路径：在一个图中，若从某顶点Vp出发，沿一些边经过顶点V1,V2,Vm到达，Vq，则称顶点序列(Vp,V1,V2,Vm,Vq)为从Vp到Vq的路径(Path)。路径长度：对于无权的图，路径长度指的是沿此路径上边的数目；对于有权图，一般是取沿路径各边的权之和作为此路径的长度。若一条路径上各顶点均不重复，即路径经过每一顶点不超过一次，则此路径叫做简单路径。如果从一个顶点出发又回到该顶点，即Vp与Vq相同，则此路径叫做环路（Cy
6、cle）。第11页，本讲稿共134页第六章 图连通、连通图：在无向图中，如果从顶点Vi到顶点Vj之间有路径，则称这两个顶点是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图(Connected graph)。连通分量：例如图7.1中的图G1是连通图。图7.4中的图就是非连通图，非连通图的每一个极大连通子图叫连通分量(Connected Component)，此图包括二个连通分量。第12页，本讲稿共134页第六章 图图7.4 非连通图G第13页，本讲稿共134页第六章 图强连通图和强连通分量：在有向图G中，如果从顶点Vi到顶点Vj和从顶点Vj到顶点Vi之间都有路径，则称这两个顶点是强连通
7、的。如果图中任何一对顶点都是强连通的，则此图叫做强连通图。非强连通图的每一个极大强连通子图叫做强连通分量。图7.1中的G2不是强连通图，它有两个强连通分量，如图7.5所示。第14页，本讲稿共134页第六章 图图7.5 图G2的强连通分量返回第15页，本讲稿共134页第六章 图7.2.1 邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵。所谓两顶点的相邻关系即它们之间有边相连。邻接矩阵是一个（nn）阶方阵，n为图的顶点数，它的每一行分别对应图的各个顶点，它的每一列也分别对应图的各个顶点。我们规定矩阵的元素为：第16页，本讲稿共134页第六章 图图7.7 无向图的邻接矩阵第17页，本讲稿共134页第六
8、章 图图7.7 有向图的邻接矩阵第18页，本讲稿共134页第六章 图无向图的邻接矩阵是对称的，如果Ai，j=1，必有Aj，i=1。这说明，只输入和存储其上三角阵元素即可得到整个邻接矩阵。一般有向图的邻接矩阵是不对称的，Ai，j不一定等于Aj，i。邻接矩阵用二维数组即可存储，定义如下：int adjmatrix=ARRAYnn;如果图的各边是带权的，只需将矩阵中的各个1元素换成相应边的权即可。第19页，本讲稿共134页第六章 图产生无向图邻接矩阵算法void creatgraph(int adjarray )int i,j,v1,v2,num;scanf(“%d”,&num);/*输入顶点数*/
9、if(num0)for(i=1;i=num;i+)for(j=1;j=num;j+)adjarry ij=0;/*矩阵初始化*/do 第20页，本讲稿共134页第六章 图产生无向图邻接矩阵算法续 scanf(“%d,%d”,&v1,&v2);/*输入边*/adjarrayv1v2=1;adjarrayv2v1=1;while(v1!=0&v2!=0);else num=0;retrun num;第21页，本讲稿共134页第六章 图7.2.2 邻接表邻接表是图的一种链接存储结构。在邻接表结构中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于该顶点Vi的边，即对于无向图每个结点表示与
10、该顶点相邻接的一个顶点；对于有向图则表示以该顶点为起点的一条边的终点。一个图的邻接矩阵表示是唯一的，但其邻接表表示是不唯一的。因为在邻接表的每个单链表中，各结点的顺序是任意的。第22页，本讲稿共134页第六章 图图7.8 邻接表图7.7中无向图对应的邻接表第23页，本讲稿共134页第六章 图图7.7中有向图对应的邻接表第24页，本讲稿共134页第六章 图邻接表中每个表结点均由两个域组成，其一是邻接点域（adjvex），用以存放与顶点Vi相邻接的顶点在图中的位置；其二是链域（next），用以指向依附于顶点Vi的下一条边所对应的结点。如果用邻接表存放网络中的信息，则还需要在结点中增加一个存放权值的
11、域。在每个链表设一表头结点，一般这些表头结点本身以向量的形式存储。第25页，本讲稿共134页第六章 图对于无向图的邻接表来说，一条边对应两个单链表结点，邻接表结点总数是边数的2倍。在无向图的邻接表中，各顶点对应的单链表的结点数（不算表头结点）就等于该顶点的度数。在有向图邻接表中，一条弧对应一个表结点，表结点的数目和弧的数目相同。在有向图邻接表中，单链表的结点数就等于相应顶点的出度数。要求有向图中某顶点的入度数，需扫视邻接表的所有单链表，统计与顶点标号相应的结点个数。第26页，本讲稿共134页第六章 图邻接表存储结构定义#define MAXVEX 30 struct edgenode int
12、adjvex;/*邻接点域*/struct edgenode*next;/*链域*/;struct vexnode char data;/*顶点信息*/struct edgenode*link;typedef struct vexnode adjlistMAXVEX;第27页，本讲稿共134页第六章 图产生无向图的邻接表算法void creategraph(adjlist g)int e,i,s,d,n;struct edgenode*p;printf(“请输入结点数(n)和边数(e):n”);scanf(“%d,%d”,&n,&e);for(i=1;i=n;i+)printf(“n请输入第%
13、d个顶点信息：”,i);scanf(“%c”,&gi.data);gi.link=NULL;for(i=1;i=e;i+)第28页，本讲稿共134页第六章 图产生无向图的邻接表算法续 printf(“n请输入第%d条边起点序号，终点序号：”,i);scanf(“%d,%d”,&s,&d);p=(struct edgenode*)malloc(sizeof(edgenode);padjvex=d;/*邻接点序号为d*/pnext=gs.link;gs.link=p;/*将新结点插入顶点Vs边表的头部*/p=(struct edgenode*)malloc(sizeof(edgenode);pad
14、jvex=s;/*邻接点序号为s*/pnext=gd.link;gd.link=p;/*将新结点插入顶点Vd边表的头部*/返回第29页，本讲稿共134页第六章 图7.3.1 深度优先搜索(DFS)首先访问图中某指定起始点Vi，然后由Vi出发访问它的任一相邻接顶点Vj，再从Vj出发访问Vj的任一未访问过的相邻接顶点Vk，再从Vk出发进行类似访问，如此进行下去，直到某顶点已没有未被访问过的相邻接顶点时，则退回一步，退到前一个顶点，找前一个顶点的其它尚未被访问的相邻接顶点。如有未访问过的相邻接顶点，则访问此顶点后，再从该顶点出发向前进行与前述类似的访问；如退回一步后，前一顶点也没有未被访问过的相邻接
15、顶点，则再向回退一步进行搜索，重复上述过程，一直到所有顶点均被访问过为止。第30页，本讲稿共134页第六章 图图7.9 图的遍历例子第31页，本讲稿共134页第六章 图由于图中的路径可能有环路，为了避免重复访问某些顶点，设计图的搜索算法时，可设置一个表示顶点是否被访问过的辅助数组visited，初始时将数组元素置零，一旦某顶点Vi被访问过，则令visitedVi=1，以后此顶点即不再访问。第32页，本讲稿共134页第六章 图深度优先搜索算法深度优先搜索是一种递归的过程，可以简单地将其表示成递归的形式，其算法描述如下：DFS(V0)访问V0顶点;visitedV0=1;对所有与V0相邻接的顶点w
16、 if(visitedw=0)DFS(w);第33页，本讲稿共134页第六章 图邻接表表示的图的DFS算法 int visitedMAXVEX;void dfsgraph(adjlist adj,int n)int i;for(i=1;i=n;i+)visitedi=0;/*给visited数组赋初值*/for(i=1;i=n;i+)if(!visitedi)dfs(adj,i);第34页，本讲稿共134页第六章 图从Vi出发进行DFS的递归算法void dfs(adjlist adj,int v)struct edgenode*p;visitedv=1;printf(“%d”,v);p=ad
17、jvlink;while(p!=NULL)if(visitedpadjvex=0)dfs(adjlist,padjvex);/*从v未访问的邻接点出发进行DFS*/p=pnext;第35页，本讲稿共134页第六章 图时间复杂性分析一个有n个顶点、e条边的图，在深度优先搜索图的过程中，找邻接点所需时间为O(e)。对辅助数组初始化时间为O(n)。因此，当用邻接表作为图的存储结构时，深度优先搜索图的时间复杂性为O(e+n)。第36页，本讲稿共134页第六章 图非递归算法从顶点Vi出发进行深度优先遍历的递归过程也可以写成非递归的形式，此时需借助一个堆栈保存被访问过的结点，以便回溯时查找已被访问结点的未
18、被访问过的邻接点。设堆栈由一个一维数组构成，数组名为stack，栈顶指针为top,假设此数组足够大,不必考虑溢出的可能。第37页，本讲稿共134页第六章 图非递归算法#define MAXVEX 100void dfs(adjlist g，int v,int n)/*从顶点v出发进行深度优先遍历*/struct vexnode *stackMAXVEX,*p;int visitedMAXVEX,top=0;for(i=1;i0|p!=NULL)第38页，本讲稿共134页第六章 图非递归算法续 while(p!=NULL)if(visitedp-adjvex=1)p=p-next;else pr
19、intf(“%d”,p-adjvex);visitedp-adjvex=1;top+;stacktop=p;p=gp-adjvex.link;第39页，本讲稿共134页第六章 图非递归算法续 if(top0)top-;/*退栈，回溯查找已被访问结点的未被访问过的邻接点*/p=stacktop;p=p-next;第40页，本讲稿共134页第六章 图7.3.2 广度优先搜索(BFS)图的广度优先搜索（BFS）类似于树的按层次遍历。广度优先搜索的基本思想是：首先访问图中某指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、Vk，并均标记为已访问过，然后再按照Vj、Vk的
20、次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止。第41页，本讲稿共134页第六章 图在广度优先搜索中，若对顶点V1的访问先于顶点V2的访问，则对V1邻接顶点的访问也先于V2邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。设此队列由一个一维数组构成，数组名为Queue，队首指针和队尾指针分别为front和rear。假设数组足够大，不必考虑有溢出的可能性。广度优先搜索不是递归过程
21、，不能用递归形式。第42页，本讲稿共134页第六章 图BFS算法描述BFS(v0)访问v0顶点；visitedv0=1;被访问过的顶点入队；当队列非空时，进行下面的循环 （1）被访问过的顶点出队；（2）对所有与该顶点相邻接的顶点w if(visitedw=0)(a)访问w顶点；(b)visitedw=1;(c)w入队;第43页，本讲稿共134页第六章 图邻接表表示的图的BFS算法int visitedMAXVEX;int queueMAXVEX;void bfs(adjlist adj,int v)int front=0,rear=1,v;struct edgenode*p;visitedv=
22、1;printf(“%d”,v);queuerear=v;/*初始顶点入队*/while(front!=rear)/*队列不为空*/第44页，本讲稿共134页第六章 图邻接表表示的图的BFS算法续 front=front+1;v=queuefront;/*按访问次序出队列*/p=adjv-link;/*找v的邻接顶点*/while(p!=NULL)if(visitedp-adjvex=0)visitedp-adjvex=1;printf(“%d”,p-adjvex);第45页，本讲稿共134页第六章 图邻接表表示的图的BFS算法续 rear=rear+1;queuerear=p-adjvex;
23、p=p-next;第46页，本讲稿共134页第六章 图时间复杂性分析一个有n个顶点、e条边的图，在广度优先搜索图的过程中，每个顶点至多进一次队列，图的搜索过程实质上是通过边来找顶点的过程，找邻接点所需时间为O(e)。对辅助数组初始化时间为O(n)。因此，当用邻接表作为图的存储结构时，广度优先搜索图的时间复杂性为O(e+n)。返回第47页，本讲稿共134页第六章 图7.4 最小生成树在一个无向连通图G中，如果取它的全部顶点和一部分边构成一个子图G，若边集E(G)中的边刚好将图的所有顶点连通但又不形成环路，我们就称子图G是原图G的生成树（Spanning tree）。生成树有如下特点：任意两个顶点
24、之间有且仅有一条路径；如果再增加一条边就会出现环路；如果去掉一条边此子图就会变成非连通图。一个有n 个顶点的完全图，一共存在n(n-2)种不同的生成树。第48页，本讲稿共134页第六章 图对于带权的连通图（连通网）G，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树（Minimum Spanning Tree）。具有n个顶点的连通图的生成树具有n-1条边（少于此边数不可能将各顶点连通，多于此边数则必然要出现环路）。第49页，本讲稿共134页第六章 图图7.10 图G 及其生成树无向连通图 G 生成树生成树 第50页，本讲稿共134页第六章 图图
25、7.10 图G 及其生成树生成树最小生成树最小生成树第51页，本讲稿共134页第六章 图7.4.1 普里姆(prim)算法假设G=(V,E)是一个具有n 个顶点的连通网络，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空。算法开始时，首先从V中任取一个顶点（假定为V1），将此顶点并入U中，此时最小生成树顶点集U=V1；然后从那些其一个端点已在U中，另一个端点仍在U外的所有边中，找一条最短（即权值最小）的边，假定该边为(Vi,Vj),其中ViU，VjV-U,并把该边(Vi,Vj)和顶点Vj分别并入T的边集TE和顶点集U；第52页，本讲稿共134页第六章
26、图如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后，把所有n 个顶点都并入生成树T的顶点集U中，此时U=V，TE中包含有（n-1）条边；这样，T就是最后得到的最小生成树。普里姆算法中每次选取的边两端，总是一个已连通顶点（在U集合内）和一个未连通顶点（在U集合外），故这个边选取后一定能将未连通顶点连通而又保证不会形成环路。第53页，本讲稿共134页第六章 图图7.11 普里姆算法例子第54页，本讲稿共134页第六章 图为了便于在顶点集合U和V-U之间选择权最小的边，建立两个数组closest和lowcost,closesti表示U中的一个顶点，该顶点与V-U中的一个顶点构成的边具
27、有最小的权；lowcost表示该边对应的权值。开始，由于U的初值为1，所以，closesti的值为1，i=2,n,而lowcosti为V1到各顶点的边中最小的权值。第55页，本讲稿共134页第六章 图普里姆算法void prim(int cMAXVEX,int n)/*c表示图的邻接矩阵，图的顶点为1,2n*/int lowcostn,closestn;int i,j k,min;for(i=2,i=n;i+)/*从顶点V1开始*/lowcosti=c1i;closesti=1;for(i=2;i=n;i+)/*从U之外求离U中某顶点最近的顶点*/第56页，本讲稿共134页第六章 图普里姆算法
28、续 min=lowcosti;k=i;for(j=2;j=n;j+)if(lowcostjmin)min=lowcostj;k=j;printf(“(%d,%d)”,k,closestj);/*打印生成树的一条边*/第57页，本讲稿共134页第六章 图普里姆算法续 lowcostk=32777;/*k加入 到U中*/for(j=2;j=n;j+)if(ckjlowcostj&lowcostj0)i=seti;return(i);第68页，本讲稿共134页第六章 图克鲁斯卡尔算法void kruskal(edgeset ge,int n,int e)/*ge为权按从小到大排序的边集数组*/int
29、 setMAXE,v1,v2,i,j;for(i=1;i=n;i+)seti=0;/*给set中每个元素赋初值*/i=1;/*i表示获取的生成树中的边数，初值为1*/j=1;/*j表示ge中的下标，初始值为1*/while(jn&i=e)/*检查该边是否加入到生成树中*/v1=seeks(set,gei.bv);第69页，本讲稿共134页第六章 图克鲁斯卡尔算法续 v2=seeks(set,gei.tv);if(v1!=v2)/*当 v1,v2不在同一集合，该边加入生成树*/printf(“(%d,%d)”,gei.bv,gei.tv);setv1=v2;j+;i+;返回第70页，本讲稿共13
30、4页第六章 图7.5 最短路径所谓最短路径（shortest path）问题指的是：如果从图中某顶点出发（此点称为源点），经图的边到达另一顶点（称为终点）的路径不止一条，如何找到一条路径使沿此路径上各边的权值之和为最小。设一有向网络G=（V,E），已知各边的权值，并设每边的权均大于零，以某指定V0为源点，求从V0到图的其余各点的最短路径。以图 7.13为例，若指定以顶点V7为源点V0，该图比较简单，通过观察可得到从V7到其余各点的最短路径。第71页，本讲稿共134页第六章 图图7.13 最短路径例子第72页，本讲稿共134页第六章 图狄克斯特拉算法狄克斯特拉于1959年提出了一个按路径“长度”
31、递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法。假设我们以邻接矩阵cost表示所研究的有向图，costij表示有向边对应权值，如果两点之间无相应方向的边，则该元素取为无穷大。在计算机中此矩阵用一个（nn）二维数组表示（n为图的顶点数），无穷大元素则可用某很大的有限值（如32777）代替。第73页，本讲稿共134页第六章 图图7.13对应的邻接矩阵 第74页，本讲稿共134页第六章 图狄克斯特拉算法需要一个顶点集合，初始时集合内只有一个源点V0，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。集合可用一维数组来表示，设此数组为S，凡在集合S以外的
32、顶点，其相应的数组元素Si为0，否则为1。还需要另一个一维数组dist，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为disti=costV0i，i=2n。数组dist中的数据随着算法的逐步进行要不断地修改。第75页，本讲稿共134页第六章 图定义了S集合和dist数组并对其初始化后，狄克斯特拉算法在进行中，都是从S之外的顶点集合中选出一个顶点w，使distw的值最小。于是从源点到达w只通过S中的顶点，把w加入集合S中，并调整dist中记录的从源点到集合中每个顶点v的距离：从原来的distv和distw+costwv中，选择较小的值作为新的distv。重复上述过
33、程，直到S中包含V中其余各顶点的最短路径。第76页，本讲稿共134页第六章 图狄克斯特拉算法#define MAXVEX 100/*定义最多顶点数*/void shortpath(int costMAXVEXMAXVEX,distMAXVEX,n,v0)int sMAXVEX,u,vnum,w,wm;for(w=1;w=n;w+)/*最短路径初始化*/distw=costv0w;for(w=1;w=n;w+)sw=0;sv0=1;/*S中顶点个数的初值*/vnum=1;第77页，本讲稿共134页第六章 图狄克斯特拉算法续while(vnumn-1)/*最后一个顶点已无选择余地*/wm=3277
34、7;u=v0;for(w=1;w=n;w+)if(sw=0&distwwm)u=w;wm=distw;/*找最小distw*/su=1;/*u为找到最短路径的终点*/vnum+;第78页，本讲稿共134页第六章 图狄克斯特拉算法续 for(w=1;w=n;w+)if(sw=0&distu+costuw distw)distw=distu+costuw;/*调整不在S集合中的顶点的最短路径*/for(w=1;w=n;w+)printf(“%d”,w);printf(“%d”,disti);/*输出结果*/第79页，本讲稿共134页第六章 图狄克斯特拉算法例子以图7.13所示的图为例来说明当指定以
35、V7为源点V0后，用狄克斯特拉算法求最短路径的动态执行情况，其表示集合的数组S和表示距离的数组dist元素值的变化如图7.14所示。第80页，本讲稿共134页第六章 图图7.14 算法动态执行情况第81页，本讲稿共134页第六章 图返回第82页，本讲稿共134页第六章 图7.7 拓扑排序在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；子项目之间无次序要求，即两个子项目可以同时进行，互不影响。在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。学校里某个专业的课程学习，有些课程是基础课，它们可
36、以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。第83页，本讲稿共134页第六章 图这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶点称之为活动(Activity)。如果从顶点Vi到Vj之间存在有向边,则表示活动i必须先于活动j进行。这种图称做顶点表示活动的网络(Activity On Vertex network,简称AOV网络)。例如图7.15是某校计算机专业的课程及其相互之间的关系，它对应的AOV网络如图7.17所示。第84页，本讲稿共134页第六章 图图7.15 某专业课程设置第85页，本讲稿共134页第六章 图图7.17 AOV网络
37、第86页，本讲稿共134页第六章 图在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。AOV网络中一定不能有有向环路。例如在图7.17那样的有向环路中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，环路表示顶点之间的先后关系进入了死循环。因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。第87页，本讲稿共134页第六章 图图7.17 有向环路第88页，本讲稿共134页第六章 图拓扑排序所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动
38、)排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。由于AOV网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必定不包含有有向环路。第89页，本讲稿共134页第六章 图拓扑排序方法(1)在网络中选择一个没有前趋的顶点，并把它输出；(2)从网络中删去该顶点和从该顶点发出的所有有向边；(3)重复执行上述两步，直到网中所有的顶点都被输出(此时，原AOV网络中的所有顶点和边就都被删除掉了)。如果进行到某一步，无法找到无前趋
39、的顶点，则说明此AOV网络中存在有向环路，遇到这种情况，拓扑排序就无法进行了。第90页，本讲稿共134页第六章 图图7.18 拓扑排序过程AOV网络 输出输出V3后后第91页，本讲稿共134页第六章 图输出V4后输出输出V2后后输出输出V1后后输出输出V5后后第92页，本讲稿共134页第六章 图为了实现拓扑排序的算法，对于给定的有向图，假定采用邻接表作为它的存储结构，每个顶点在邻接表中对应一个单链表，表示该顶点的各直接后继顶点。规定将每个结点的Data域改为int型，并将每个链表的表头结点构成一个顺序表，各表头结点的Data域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得
40、到。例如图7.18有向图生成的邻接表如图7.19所示。第93页，本讲稿共134页第六章 图图7.19 AOV网络的邻接表第94页，本讲稿共134页第六章 图在拓扑排序过程中，凡入度为零的顶点即是没有前趋的顶点，可将其取出列入有序序列中，同时将该顶点从图中删除掉不再考虑。删去一个顶点时，所有它的直接后继顶点入度均减1，表示相应的有向边也被删除掉。设置一个堆栈，将已检验到的入度为零的顶点标号进栈，当再出现新的无前趋顶点时，也陆续将其进栈。每次选入度为零的顶点时，只要取栈顶顶点即可。第95页，本讲稿共134页第六章 图设计算法时，可借用表头结点的Data域构成一个链接堆栈。用该数据域存放下一个入度为
41、零的顶点标号，将堆栈中的各个单元链接起来，再设置一个栈顶指针top即可。右图为表示图7.19的链接堆栈。第96页，本讲稿共134页第六章 图用邻接表存储AOV网络，实现拓扑排序的步骤可描述如下：(1)把邻接表中所有入度为零的顶点进栈；(2)在栈不空时：退栈并输出栈顶的顶点j；在邻接表的第i个单链表中，查找顶点为j的所有直接后继顶点k，并将顶点k的入度减1。若顶点k的入度为零，则顶点k进栈；若栈空时输出的顶点个数不是n,则有向图中有环路，否则拓扑排序完毕。第97页，本讲稿共134页第六章 图拓扑排序算法void topsort(adjlist adj,int n)/*adj为邻接表*/int n
42、um,i,j,top;struct vexnode*q;top=0;num=0;/*num指示输出顶点个数*/for(i=1;idata=0)adji-data=top;top=i;第98页，本讲稿共134页第六章 图拓扑排序算法续 while(top0)i=top;top=adji-data;/*在链表中删除入度为0的顶点，顶点序号为i*/q=adji-link;printf(“%d”,i);/*输出顶点Vi并计数*/num+;while(q!=NULL)j=q-adjvex;adjj-data-;/*将后继结点j的入度减1*/第99页，本讲稿共134页第六章 图拓扑排序算法续 if(adj
43、j-data=0)adjj-data=top;top=j;q=p-next;/*找下一个后继结点*/if(numn)printf(“网络中有环路!”n);/*因输出的顶点数小于n*/返回第100页，本讲稿共134页第六章 图7.7 关键路径法关键路径法是采用边表示活动(Activity On Edge)的网络，简称为AOE网络。AOE网络是一个带权的有向无环路图，其中，每个顶点代表一个事件(Event)，事件说明某些活动或某一项活动的完成，即阶段性的结果。离开某顶点的各条边所代表的活动，只有在该顶点对应的事件出现后才能开始。权值表示活动持续的时间。第101页，本讲稿共134页第六章 图图7.2
44、0 一个AOE网络第102页，本讲稿共134页第六章 图AOE网络通常利用AOE网络可以研究以下两个问题：(1)完成整个工程至少需要多少时间？(2)哪些活动是影响工程进度的关键？第103页，本讲稿共134页第六章 图关键路径完成工程所需的时间就是从开始点起进行到结束点止所需的时间。路径长度是指沿路径各边的权值之和，也就是这些边所代表的活动所需时间之和。完成整个工程所需的时间取决于从开始点到结束点的最长路径长度，此长度最大的路径叫做关键路径。分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的效率，缩短整个工期。第104页，本讲稿共134页第六章 图在描述关键路径的算法时，设活动ai由
45、弧表示，要确定如下几个相关的量：(1)事件Vj的最早出现时间和活动的最早开始时间：从源点V1到某顶点Vj的最长路径长度叫作事件j的最早出现时间，表示成evj。顶点Vj的最早出现时间evj决定了从Vj指出的各条边所代表活动的最早开始时间，因为事件j不出现，它后面的各项活动就不能开始。我们以ei表示活动ai的最早开始时间。显然ei=evj。第105页，本讲稿共134页第六章 图(2)活动ai的最迟开始时间：在不影响整个工程按时完成的前提下，此项活动最迟的必须开始时间，表示成Li。只要某活动ai有Li=ei的关系，我们就称ai为关键活动。关键活动只允许在一个确定的时间开始，再早，它前面的事件还没出现
46、，尚不能开始；再晚，又会延误整个工程的按时完成。由于完成整个工程所需的时间是由关键路径上各边权值之和所决定的，显然关键路径上各条边所对应的活动都是关键活动。第106页，本讲稿共134页第六章 图(3)事件j的最迟出现时间：即事件j在不延误整个工程的前提下允许发生的最迟时间，表示为Lvj。对某条指向顶点Vj的边所代表的活动ai可得到：Li=Lvj-(活动ai所需时间)也就是活动ai必须先于它后面事件的最迟出现时间开始，提前的时间为进行此活动所需的时间。图7.21所示为活动开始时间与事件出现时间的关系。第107页，本讲稿共134页第六章 图图7.21 活动开始时间与事件出现时间的关系 第108页，
47、本讲稿共134页第六章 图确定关键路径的方法就是要确定ei=Li的关键活动。假设以wj,k表示有向边的权，即此边对应的活动所需的时间，为了求AOE网络中活动ai的最早开始时间ei和活动ai的最迟开始时间Li，先要求得顶点Vk的事件Vk的最早出现时间evk和最迟出现时间Lvk。第109页，本讲稿共134页第六章 图evk和Lvk可以采用下面的递推公式计算：(1)向汇点递推 由源点的ev1=0开始，利用公式：向汇点的方向递推，可逐个求出各顶点的ev。式中p表示所有指向顶点的边的集合，如图7.22所示。第110页，本讲稿共134页第六章 图图7.22 集合p此式的意义为：从指向顶点Vk的各边的活动中
48、取最晚完成的一个活动的完成时间作为Vk的最早出现时间evk。第111页，本讲稿共134页第六章 图(2)向源点递推 由上一步的递推，最后总可求出汇点的最早出现时间evn。因汇点就是结束点，最迟出现时间与最早出现时间相同，即Lvn=evn。从汇点的最迟出现时间Lvn开始，利用下面公式：向源点的方向往回递推，可逐个求出各顶点的最迟出现时间Lv。式中s表示所有由Vj点指出的边的集合，如图7.23所示。第112页，本讲稿共134页第六章 图图7.23 集合s此公式的意义为：由从Vj顶点指出的各边所代表的活动中取需最早开始的一个开始时间作为Vj的最迟出现时间。第113页，本讲稿共134页第六章 图无论是
49、向汇点递推还是向源点递推，都必须按一定的顶点顺序进行。对所有的有向边，向汇点递推是先求出尾顶点的ev值，再求头顶点的ev值；向源点递推则相反，先求头顶点的Lv值，再求尾顶点的Lv值。为此，可利用上节介绍的拓扑排序得到的顶点次序进行向汇点的递推，向源点的递推按相反的顺序进行即可，不必再重新排序。第114页，本讲稿共134页第六章 图关键路径算法(1)输入e条有向边，建立AOE网络的存储结构；(2)从源点出发，令ev1=0，按拓扑排序的序列求其余各顶点的最早出现时间evi(2in)。若拓扑排序序列中的顶点个数小于网络中的顶点数n，则说明网络中存在环路，算法中止执行；否则执行(3)；第115页，本讲
50、稿共134页第六章 图(3)从汇点Vn出发，令Lvn=evn，按逆拓扑排序的序列求其余各顶点的最迟出现时间 Lvi(n-1i1)；(4)根据各顶点的ev和Lv值求每条有向边ai的最早开始时间ei和最迟开始时间Li。若某有向边ai满足ei=Li,则为关键活动。对图7.20例子中的AOE网络，各事件的最早出现时间和最迟出现时间及各活动的最早开始时间和最迟开始时间计算结果如表7.1所示。第116页，本讲稿共134页第六章 图表7.1 AOE网络中的关键活动第117页，本讲稿共134页第六章 图由表7.1可知时间余量为零的活动都是关键活动，即为a1，a4，a7，a8，a10，a11。这些关键活动构成两