数据结构之图ppt课件

数据结构之图课件数据结构之图课件1第7章 图知 识 点图的逻辑结构特征及图的基本术语邻接矩阵和邻接表两种图的存储结构的特点及适用范围深度优先搜索和广度优先搜索两种遍历算法的特点和执行过程生成树和最小生成树的概念及构造最小生成树的prim和kruskal算法最短路径的含义及求最短路径的算法拓扑排序的基本思想和步骤关键路径法及其在管理科学中的作用第7章 图知 识 点2数据结构之图ppt课件3数据结构之图ppt课件4图7.1 有向图与无向图无向图G1有向图有向图G2图7.1 有向图与无向图无向图G1有向图G25完全图：在一个有n个顶点的无向图中，若每个顶点到其它（n-1）个顶点都连有一条边，这种图称为完全图。完全图中共有n(n-1)/2条边，（Complete graph，也称完备图）。左图所示就是左图所示就是n=4的完全图，它一的完全图，它一共有六条边。共有六条边。完全图：在一个有n个顶点的无向图中，若每个顶点到其它（n-16权和网络：有些图，对应每条边有一相应的数值，这个数值叫做该边的权(Weight)。边上带权的图称为带权图，也称为网络(Network)。子图：设有两个图G=(V,E)和G=(V,E)，若V(G)V(G)，E(G)E(G)，则称G是G的子图(Subgraph)。例如图6.3所示的图是图6.1中G1的一些子图。权和网络：有些图，对应每条边有一相应的数值，这个数值叫做该7图7.3 子图图7.3 子图8顶点的度：图中与每个顶点相连的边数，叫该顶点的度(Degree)，记作TD（V）。入度、出度：对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。分别记作 ID（V），OD（V）。顶点的度：图中与每个顶点相连的边数，叫该顶点的度(Degre9路径（回路）：若从某顶点Vp出发，沿一些边经过顶点V1,V2,Vm到达，Vq，则称顶点序列(Vp,V1,V2,Vm,Vq)为从Vp到Vq的路径(Path)。若其中间顶点不重复，则称简单路径；若第1个顶点和最后一个顶点相同，则称为回路。路径长度：对于无权的图，路径长度指的是沿此路径上边的数目；对于有权图，一般是取沿路径各边的权之和作为此路径的长度。路径（回路）：若从某顶点Vp出发，沿一些边经过顶点V1,V210连通、连通图：在无向图中，如果从顶点Vi到顶点Vj之间有路径，则称这两个顶点是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图(Connected graph)。连通分量：非连通图的每一个极大连通子图叫连通分量(Connected Component)。连通、连通图：在无向图中，如果从顶点Vi到顶点Vj之间有路径11图7.4 非连通图G图7.4 非连通图G12强连通图和强连通分量：在有向图G中，如果从顶点Vi到顶点Vj和从顶点Vj到顶点Vi之间都有路径，则称这两个顶点是强连通的。如果图中任何一对顶点都是强连通的，则此图叫做强连通图。非强连通图的每一个极大强连通子图叫做强连通分量。生成树：有n个顶点，n-1条边的树，且 V=V，EE。强连通图和强连通分量：在有向图G中，如果从顶点Vi到顶点Vj13图7.5 图G2的强连通分量返回图7.5 图G2的强连通分量返回147.2 图的存储结构1。邻接矩阵表示法邻接矩阵是表示顶点之间相邻关系的矩阵。所谓两顶点的相邻关系即它们之间有边相连。若图有n个结点数，邻接矩阵是一个（nn）阶方阵。对无权图，7.2 图的存储结构1。邻接矩阵表示法15图7.6 无向图的邻接矩阵图7.6 无向图的邻接矩阵16图7.7 有向图的邻接矩阵图7.7 有向图的邻接矩阵17可以看出:1.无向图的邻接矩阵是对称的，2.即若Ai，j=1，必有Aj，i=1。所以，只存储其上三角阵元素即可.3.2.对无向图,结点Vi的度,是邻接矩阵中,第i行1的个数.可以看出:18对有向图有向图,邻接矩阵一般是不对称的，Ai，j不一定等于Aj，i。结点Vi的出度OD(Vi),是邻接矩阵中,第i行1的个数.结点Vi的入度ID(Vi),是邻接矩阵中,第i列1的个数.对有向图,邻接矩阵一般是不对称的，Ai，j不一定等于A19 对于有权图有权图(网）网）例：例：对于有权图(网）20邻接矩阵用二维数组即可存储，定义如下：int adjmatrix ARRAYnn;邻接矩阵用二维数组即可存储，定义如下：21产生无向图邻接矩阵算法void creatgraph(int adjarray )int i,j,v1,v2,num;scanf(“%d”,&num);/*输入顶点数*/if(num0)for(i=1;i=num;i+)for(j=1;j=num;j+)adjarry ij=0;/*矩阵初始化*/产生无向图邻接矩阵算法void creatgraph(in22 do scanf(“%d,%d”,&v1,&v2);/*输入边*/adjarrayv1v2=1;adjarrayv2v1=1;while(v1!=0&v2!=0);else num=0;retrun（num）;do scanf(“%d,%d”,&v232.邻接表邻接表是图的一种链接存储结构。在邻接表结构中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示与结点Vi相关连的边；对于有向图则表示以该顶点为起点的一条边的终点。一个图的邻接矩阵表示是唯一的，但其邻接表表示是不唯一的。因为在邻接表的每个单链表中，各结点的顺序是任意的。2.邻接表邻接表是图的一种链接存储结构。24有两种结点：1.表头结点：每个链表设一表头结点 Vexdata firstarcVexdata：结点信息Firstarc:第一条边有两种结点：Vexdata firstarcVexda25 2.边表结点：vertex：存放与顶点Vi相邻接的顶点 nextarc：指向依附于顶点Vi的下一条边所对 应的结点 Info：有权图有权图（网络）网络）中边的权值 例：无向图，有向图vertex infonextarc vertex infonextarc26图7.6中无向图对应的邻接表图7.6中无向图对应的邻接表27图7.7中有向图对应的邻接表图7.7中有向图对应的邻接表28对于无向图无向图的邻接表来说，一条边对应两个单链表结点，邻接表结点总数是边数的2倍。在无向图无向图的邻接表中，各顶点对应的单链表的结点数（不算表头结点）就等于该顶点的度数。在有向图有向图邻接表中，一条弧对应一个表结点，表结点的数目和弧的数目相同。在有向图有向图邻接表中，单链表的结点数就等于相应顶点的出度数。有向图有向图中某顶点的入度数，需扫描邻接表的所有单链表，统计与顶点标号相应的结点个数。对于无向图的邻接表来说，一条边对应两个单链表结点，邻接表结点29邻接表存储结构定义#define maxvex 30 typedef struct edgenode /*边表结点*/int adjvex;/*邻接点域*/infotype info;/*边的信息*struct edgenode*nextarc;/*一条边的顶点*/edgenode;Typedef struct vexnode /*表头结点*/char vexdata;edgenode*firstarc;vexnode;vexnode adjlistmaxvex;邻接表存储结构定义#define maxvex 3030产生无向图的邻接表算法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请 输 入 第%d个 顶 点 信 息：”,i);scanf(“%c”,&gi.data);gi.link=NULL;for(i=1;i=e;i+)产生无向图的邻接表算法void creategraph(a31产生无向图的邻接表算法(续)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);padjvex=s;/*邻接点序号为s*/pnext=gd.link;gd.link=p;/*将新结点插入顶点Vd边表的头部*/返回产生无向图的邻接表算法(续)printf(“32 3.十字链表法 对有向图,也可采用十字链表法4.邻接多重表存储法用于无向图 3.十字链表法337.3 图的遍历1。深度优先搜索(DFS)首先访问图中某指定起始点Vi，然后由Vi出发访问它的任一相邻接顶点Vj，再从Vj出发访问Vj的任一未访问过的相邻接顶点Vk，再从Vk出发进行类似访问，如此进行下去，直到某顶点已没有未被访问过的相邻接顶点时，则退回一步，退到前一个顶点，找前一个顶点的其它尚未被访问的相邻接顶点。如有未访问过的相邻接顶点，则访问此顶点后，再从该顶点出发向前进行与前述类似的访问；如退回一步后，前一顶点也没有未被访问过的相邻接顶点，则再向回退一步进行搜索，重复上述过程，一直到所有顶点均被访问过为止。7.3 图的遍历1。深度优先搜索(DFS)34图7.9 图的遍历例子图7.9 图的遍历例子35由于图中的路径可能有环路，为了避免重复访问某些顶点，设计图的搜索算法时，可设置一个表示顶点是否被访问过的辅助数组visited，初始时将数组元素置零，一旦某顶点Vi被访问过，则令visitedVi=1，以后此顶点即不再访问。由于图中的路径可能有环路，为了避免重复访问某些顶点，设计图的36邻接表表示的图的DFS算法 adjlist为邻接表，从v0开始深度优先深度优先遍历 void DFStraverse(adjlist)for(i=0;in;i+)visitedi=0;/*给visited数组赋初值*/for(i=0;ivertex;if(visitedv=0)/*若v未访问 stack+top=p-next;visit(adjlistv.vexdata);visitedv=1;p=adjlistv.firstarc;else p=p-next;do 42 if(top!=-1)p=stacktop-;while(p!=null)or(top!=-1)/*为真返回,/*为假结束 if(top!=-1)432.广度优先搜索(BFS)图的广度优先搜索（BFS）类似于树的按层次遍历。广度优先搜索的基本思想是：首先访问图中某指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、Vk，并均标记为已访问过，然后再按照Vj、Vk的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止。2.广度优先搜索(BFS)图的广度优先搜索（BFS）类似于44在广度优先搜索中，若对顶点V1的访问先于顶点V2的访问，则对V1邻接顶点的访问也先于V2邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。设此队列由一个一维数组构成，数组名为Queue，队首指针和队尾指针分别为front和rear。假设数组足够大，不必考虑有溢出的可能性。广度优先搜索不是递归过程，不能用递归形式。在广度优先搜索中，若对顶点V1的访问先于顶点V2的访问，则对45BFS算法描述BFS(v0)访问v0顶点；visitedv0=1;被访问过的顶点入队；当队列非空时，进行下面的循环 （1）被访问过的顶点出队；（2）对所有与该顶点相邻接的顶点w if(visitedw=0)(a)访问w顶点；(b)visitedw=1;(c)w入队;BFS算法描述BFS(v0)46邻接表表示的图的BFS算法int visitedMAXVEX;int queueMAXVEX;void bfs(adjlist adj,int v)int front=0,rear=1,v;struct edgenode*p;visitedv=1;printf(“%d”,v);queuerear=v;/*初始顶点入队*/while(front!=rear)/*队列不为空*/邻接表表示的图的BFS算法int visitedMAXVE47邻接表表示的图的BFS算法(续)front=front+1;v=queuefront;/*按访问次序出队列*/p=adjv-link;/*找v的邻接顶点*/while(p!=NULL)if(visitedp-adjvex=0)visitedp-adjvex=1;printf(“%d”,p-adjvex);邻接表表示的图的BFS算法(续)48邻接表表示的图的BFS算法续 rear=rear+1;queuerear=p-adjvex;p=p-next;邻接表表示的图的BFS算法续 49时间复杂性分析一个有n个顶点、e条边的图，在广度优先搜索图的过程中，每个顶点至多进一次队列，图的搜索过程实质上是通过边来找顶点的过程，找邻接点所需时间为O(e)。对辅助数组初始化时间为O(n)。因此，当用邻接表作为图的存储结构时，广度优先搜索图的时间复杂性为O(e+n)。返回时间复杂性分析一个有n个顶点、e条边的图，在广度优先搜索图的507.4 最小生成树在一个无向连通图G中，如果取它的全部顶点和一部分边构成一个子图G，若边集E(G)中的边刚好将图的所有顶点连通但又不形成环路，我们就称子图G是原图G的生成树（Spanning tree）。生成树有如下特点：任意两个顶点之间有且仅有一条路径；如果再增加一条边就会出现回路；如果去掉一条边此子图就会变成非连通图。一个有n 个顶点的完全图，一共存在n(n-2)种不同的生成树。7.4 最小生成树在一个无向连通图G中，如果取它的全部顶点和51对于带权的连通图（连通网）G，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树（Minimum Spanning Tree）。具有n个顶点的连通图的生成树具有n-1条边（少于此边数不可能将各顶点连通，多于此边数则必然要出现回路）。对于带权的连通图（连通网）G，其生成树也是带权的。我们把生成52图7.10 图G 及其生成树无向连通图 G 生成树生成树 图7.10 图G 及其生成树无向连通图 G 生成树 53图7.10 图G 及其生成树生成树最小生成树最小生成树图7.10 图G 及其生成树生成树最小生成树541.普里姆(prim)算法基本思想：假设N=（V，E）是连通的，TE是N上最小生成树中的边集。首先从某一结点U。开始，令U=U。，TE=，重复下列工作：从一个顶点在U中，另一个顶点在V-U中，找权值最小的边,并加入集合TE中，同时，V。加入U 中。直到U=V为止。此时，有n-1条边，T=（V，TE）为N的最小生成树。1.普里姆(prim)算法基本思想：假设N=（V，E）是连通55 假设G=(V,E)是一个具有n 个顶点的连通网络，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空。算法开始时，首先从V中任取一个顶点（假定为V。），将此顶点并入U中，此时最小生成树顶点集U=V。；数据结构之图ppt课件56 然后,从那些其一个端点已在U中，另一个端点在V-U中，找一条最短（即权值最小）的边，假定该边为(Vi,Vj),其中ViU，VjV-U,并把该边(Vi,Vj)和顶点Vi分别并入T的边集TE和顶点 集U中.如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后，把所有n 个顶点都并入生成树T的顶点集U中，此时U=V，TE中包含有（n-1）条边；这样，T就是最后得到的最小生成树。然后,从那些其一个端点已在U中，另一个57普里姆算法中每次选取的边两端，总是一个在 U 中，一个在 V-U 中，故这个边选取后一定能将未连通顶点连通而又保证不会形成环路。普里姆算法中每次选取的边两端，总是一个在 U 中，一个在 V58图6.11 普里姆算法例子图6.11 普里姆算法例子59为了便于在顶点集合U和V-U之间选择权最小的边，需建立一个数组closedgev,(vV-U),记录从U到V-U之间权最小的边.closedgev有两个字段:closedgev.vex:存放与该边相关联的在U中的顶点,closedgev.lowcost:存放该边的权.为了便于在顶点集合U和V-U之间选择权最小的边，需建立一个数60普里姆算法:void prim(gn,1)/*gn:图的邻接矩阵，顶点为 /*1,2,n,从顶点1开始 for(i=2,i=n;i+)/*从顶点2开始初始化*/closedgei.vex=1;closedgei.lowcost=gn1,i;closedge1.lowcost=0;/*顶点1加入U中.普里姆算法:61 For(i=1;i,=n-1;i+)/*求n-1条边 j=min(closedge);/*jV-U printf(“”,closedge j.vex,j);/*输出一条边 closedge j.lowcost=0;/*顶点j加入U中.for(k=1;k=n;k+)if(gn j,k closedge k.lowcost;closedgek.lowcost=gnj,k;closedgek.vex=j ;For(i=1;i,0)i=seti;return(i);查找一个顶点所属的分量函数如下：72克鲁斯卡尔算法void kruskal(edgeset ge,int n,int e)/*ge为权按从小到大排序的边集数组*/int 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);克鲁斯卡尔算法void kruskal(edgeset g73克鲁斯卡尔算法续 v2=seeks(set,gei.tv);if(v1!=v2)/*当 v1,v2不在同一集合，该边加入生成树*/printf(“(%d,%d)”,gei.bv,gei.tv);setv1=v2;j+;i+;返回克鲁斯卡尔算法续 v2=seeks(set,747.5 最短路径所谓最短路径（shortest path）问题指的是：如果从图中某顶点出发（此点称为源点），经图的边到达另一顶点（称为终点）的路径不止一条，如何找到一条路径,使沿此路径上各边的权值之和为最小。设一有向网络G=（V,E），已知各边的权值，并设每边的权均大于零，以某指定V0为源点，求从V0到图的其余各点的最短路径。例：7.5 最短路径所谓最短路径（shortest path）问75狄克斯特拉算法狄杰斯特拉于1959年提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法。假设我们以邻接矩阵cost表示所研究的有向图，costij表示有向边 对应权值，如果两点之间无相应方向的边，则其值为。在计算机中此矩阵用一个（nn）二维数组表示（n为图的顶点数)。狄克斯特拉算法狄杰斯特拉于1959年提出了一个按路径“长度”761.定义集合 SV,初值为S=V0 一维数组dist:disti 表示从V0到Vi的最 短路径,其初值为邻接矩阵costi,*.2.选择Vj,使 distj=min disti|Vi V-S 并令S=SVj3.修改所有的V-S中顶点Vi的最短路径disti.若 disti distj+costj,i 则 disti=distj+costj,i4.重复第2,3步 n-1次.1.定义集合 SV,初值为S=V077Void shortpath(cost,V0,dist,path)for(i=0;in;i+)/*最短路径初始化*/disti=cost0,i;if(distimax)pathi=0+i;/*集合的并运算 else pathi=;s=0;/*S为已找到的最短路径的终点集合Void shortpath(cost,V0,dist,pa78 For(k=0;kn-1;k+)wm=max;j=0;/*wm:临时变量 for(i=0;in;i+)/*选择最小的disti if(i!S)&(distiwm)j=i;wm=disti;S=S+j;/*集合的并运算 For(i=0;i distj+cost j,i)disti=distj+cost j,i;Pathi=path j+i;For(k=0;kn-1;k+)79狄杰斯特拉算法例子以图7.13所示的图为例来说明当指定以V6为源点V0后，用狄克斯特拉算法求最短路径的动态执行情况，其表示集合的数组S和表示距离的数组dist元素值的变化如图6.14所示。狄杰斯特拉算法例子以图7.13所示的图为例来说明当指定以V680图7.14 算法动态执行情况图7.14 算法动态执行情况81返回返回827.6 拓扑排序在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；子项目之间无次序要求，即两个子项目可以同时进行，互不影响。在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。7.6 拓扑排序在工程实践中，一个工程项目往往由若干个子项目83这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶顶点称之为活动点称之为活动(Activity)。如果从顶点Vi到Vj之间存在有向边边,则表示活动之间的优先关系活动之间的优先关系。这种图称做网络(Activity On Vertex network,简称AOV网络)。例如图6.15是某校计算机专业的课程及其相互之间的关系，它对应的AOV网络如图6.16所示。这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、84图7.15 某专业课程设置图7.15 某专业课程设置85图7.16 AOV网络图7.16 AOV网络86在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。AOV网络中一定不能有有向环路。例如在图7.17那样的有向环路中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，环路表示顶点之间的先后关系进入了死循环。因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进87图7.17 有向环路图7.17 有向环路88拓扑排序所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动)排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。由于AOV网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必定不包含有有向环路。拓扑排序所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活89拓扑排序算法1.在网络中选择一个没有前趋的顶点，并把 它输出；3.从网络中删去该顶点和从该顶点发出的所 有有向边；3.重复执行上述两步，直到网中所有的顶点 都被输出。如果进行到某一步，无法找到无前趋的顶点，则说明此AOV网络中存在有向回路。拓扑排序算法1.在网络中选择一个没有前趋的顶点，并把 90图7.18 拓扑排序过程AOV网络 输出输出V3后后图7.18 拓扑排序过程AOV网络 输出V3后91输出V4后输出输出V2后后输出输出V1后后输出输出V5后后输出V4后输出V2后输出V1后输出V5后92为了实现拓扑排序的算法，对于给定的有向图，假定采用邻接表作为它的存储结构，每个顶点在邻接表中对应一个单链表，表示该顶点的各直接后继顶点。规定将每个结点的Data域改为int型，并将每个链表的表头结点构成一个顺序表，各表头结点的Data域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。例如图7.18有向图生成的邻接表如图7.19所示。为了实现拓扑排序的算法，对于给定的有向图，假定采用邻接表作为93图7.19 AOV网络的邻接表图7.19 AOV网络的邻接表94在拓扑排序过程中，凡入度为零的顶点即是没有前趋的顶点，可将其取出列入有序序列中，同时将该顶点从图中删除掉不再考虑。删去一个顶点时，所有它的直接后继顶点入度均减1，表示相应的有向边也被删除掉。设置一个堆栈，将已检验到的入度为零的顶点标号进栈，当再出现新的无前趋顶点时，也陆续将其进栈。每次选入度为零的顶点时，只要取栈顶顶点即可。在拓扑排序过程中，凡入度为零的顶点即是没有前趋的顶点，可将其95设计算法时，可借用表头结点的Data域构成一个链接堆栈。用该数据域存放下一个入度为零的顶点标号，将堆栈中的各个单元链接起来，再设置一个栈顶指针top即可。右图为表示图6.19的链接堆栈。设计算法时，可借用表头结点的Data域构成一个链接堆栈。用该96用邻接表存储AOV网络，实现拓扑排序的步骤可描述如下：1。把邻接表中所有入度为零的顶点进栈；2。在栈不空时：退栈并输出栈顶元素i；在邻接表的第i个单链表中，查找顶点i的所有直接后继k，并将顶点k的入度减1。若顶点k的入度为零，则顶点k进栈；若栈空时输出的顶点个数不是n,则有向图中有环路，否则拓扑排序完毕。用邻接表存储AOV网络，实现拓扑排序的步骤可描述如下：97拓扑排序算法void topsort(adjlist adj,int n)/*adj为邻接表*/int num,i,j,top;struct vexnode*q;top=0;num=0;/*num指示输出顶点个数*/for(i=1;idata=0)adji-data=top;top=i;拓扑排序算法void topsort(adjlist adj98拓扑排序算法续 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*/拓扑排序算法续 while(top0)99拓扑排序算法续 if(adjj-data=0)adjj-data=top;top=j;q=p-next;/*找下一个后继结点*/if(numn)printf(“网络中有环路!”n);/*因输出的顶点数小于n*/返回拓扑排序算法续 if(adjj-1007.7 关键路径关键路径法是采用边表示活动(Activity On Edge)的网络，简称为AOE网络。AOE网络是一个带权的有向无环路图，其中，每个顶点代表一个事件事件(Event)，事件说明某些活动或某一项活动的完成，即阶段性的结果。离开某顶点的各条边所代表的活动，只有在该顶点对应的事件出现后才能开始。权值表示活动持续的时间。7.7 关键路径关键路径法是采用边表示活动(Activity101图7.20 一个AOE网络图7.20 一个AOE网络102源点 汇点要研究的问题：1.完成整个工程至少需要多少时间？2.哪些活动影响工程进度？源点 汇点103关键路径 在AOV网络中,有些活动是可以平行进行的,所以完成工程的最短时间是从开始点到终点的最长路径的长度.长度最长的路径称为关键路径.在关键路径上的活动叫关键活动.分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的效率，缩短整个工期。关键路径 在AOV网络中,有些活动是可以平104约定:e(i):活动ai的最早开始时间 如 e(9)=7 e(7)=7 L(i):活动ai的最迟开始时间,即在不影响整个 工程进度的情况下,活动ai最迟必须开始 的时间.如 L(9)=10 L(7)=7 显然,L(i)-e(i)是活动ai的时间余量(余地),若 L(i)-e(i)=0,活动ai一定是关键活动.约定:105为了求出关键活动,就要求出活动的最早开始时间e(i)和最迟开始时间L(i),为了求出活动的最早时间和最迟时间,首先要求出事件的最早发生时间和最迟发生时间.Ve(i):事件 vi 的最早发生时间 VL(i):事件 vi 的最迟发生时间为了求出关键活动,就要求出活动的最早开始时间e(i)和最迟1061.e(i)=ve(j)l(i)=vl(k)-dur(j,k)2.从ve(1)=0开始，向后递退推 Ve(j)=maxve(i)+dur(i,j)aijkji1i2im.1.aijkji1i2im1073.从 vl(n)=ve(n)起，向前递推 Vl(i)=minvl(j)-dur(i,j)ij1j2jm3.从 vl(n)=ve(n)起，向前递推ij1j2jm108求关键路径算法1.输入e条有向边，建立AOE网络的存储结构(可用邻接表等).2.从源点出发v1出发，令ve(1)=0，按拓扑排序的序列求出其余各点的最早发生时间ve(i)(用公式2)。(若拓扑排序序列中的顶点个数小于网络 中的顶点数，则说明网络中存在环路，算 法中止执行.)求关键路径算法1.输入e条有向边，建立A1093.从汇点Vn出发，令VLn=Ven，按逆拓扑排序的序列求其余各点的最迟发生时间 VL(i).(用公式3)4.根据各点的ve和VL值,求出每条边ai的最早开始时间e(i)和最迟开始时间L(i)(用公式1)。若某条边ai 满足ei=Li,则ai为关键活动。3.从汇点Vn出发，令VLn=Ven，按逆拓扑排110例7.1已知一有向图的邻接表存储结构如图7.24所示，分别给出从顶点v1出发进行深度优先和广度优先遍历所得到的顶点序列。例7.1已知一有向图的邻接表存储结构如图7.24所示，分别给111图7.24 一个有向图的邻接表图7.24 一个有向图的邻接表112例7.1解答解：根据有向图的深度优先遍历算法，从顶点v1出发所得到的顶点序列是：v1，v3，v4，v5，v2 根据有向图的广度优先遍历算法，从顶点v1出发所得到的顶点序列是：v1，v3，v2，v4，v5例7.1解答解：根据有向图的深度优先遍历算法，从顶点v1出发113例7.2有n个顶点的无向图或有向图采用邻接矩阵和邻接表表示，请回答下列问题:(1)如何计算图中有多少条边？(2)如何判断任意两个顶点i和j是否有边相连？(3)如何计算任意一个顶点的度是多少？例7.2有n个顶点的无向图或有向图采用邻接矩阵和邻接表表示，114例7.2解答解：(1)对于无向图邻接矩阵中“1”的个数除2为图的边数。邻接表中的各单链表中的结点数除2为图的边数。对于有向图邻接矩阵中“1”的个数为图的边数。邻接表中的各单链表中的结点数为图的边数。(2)对于无向图，在邻接矩阵中第i行第j列元素为“1”，或者第j行第i列元素为“1”，则顶点i与j有边相连。在邻接表中的第i个单链表中有结点为j，或者第j个单链表中有结点为i，则顶点i与j有边相连。例7.2解答解：(1)对于无向图邻接矩阵中“1”的个数除2115 对于有向图，在邻接矩阵中第i行第j列元素为“1”，则有一条从i到j的边。在邻接表中的第i个单链表中有结点为j，则有一条从i到j的边。(3)对于无向图邻接矩阵中第i行的元素之和为i顶点的度，邻接表中的第i个单链表中的结点数为i顶点的度。对于有向图邻接矩阵中第i行元素之和为i顶点的入度，第j列元素之和为j顶点的出度。在邻接表中，第i个单链表的结点数就是i顶点的出度，整个邻接表中具有的结点为i的结点数就是i顶点的入度。返回 对于有向图，在邻接矩阵中第i行第j列元116小 结图图的存储结构邻接矩阵邻接表图的遍历深度优先搜索广度优先搜索图的应用最小生成树最短路径问题利用AOV网络研究拓扑排序问题利用AOE网络研究关键路径的方法返回小 结图返回117习题与练习一、基本知识题1.图的逻辑结构特点是什么？什么是无向图和有向图？什么是子图？什么是网络？2.什么是顶点的度？什么是路径？什么是连通图和非连通图？什么是非连通图的连通分量？3.给出图6.25所示的无向图G的邻接矩阵和邻接表两种存储结构。习题与练习一、基本知识题118图7.25 一个无向图G图7.25 一个无向图G1194.假设图的顶点是A、B请根据下面的邻接矩阵画出相应的无向图或有向图。(a)(b)4.假设图的顶点是A、B请根据下面的邻接矩阵画出相应的120图7.26 一个无向图G5.分别给出图6.26所示G图的深度优先搜索和广度优先搜索得到的顶点访问序列。图7.26 一个无向图G5.分别给出图6.26所示G图的121图7.27 一个带权连通图G6.应用prim算法求图6.27所示带权连通图的最小生成树。图7.27 一个带权连通图G6.应用prim算法求图6.122图7.28 一个有向图G7.写出图6.28所示有向图的拓朴排序序列。图7.28 一个有向图G7.写出图6.28所示有向图的拓123二、算法设计题1.如图6.29所示图G，试给出其对应的邻接表，并写出深度优先算法。2.如图6.29所示图G，试给出其对应的邻接矩阵，并写出广度优先算法。3.编写一个函数通过与用户交互建立一个有向图的邻接表。4.编写一个无向图的邻接矩阵转换成邻接表的算法。二、算法设计题124图7.29 一个无向图G图7.29 一个无向图G1255.已知一个有n个顶点的有向图的邻接表，设计算法分别实现1)求出图中每个顶点的出度。2)求出图中每个顶点的入度。3)求出图中出度最大的一个顶点，输出其顶点序号。4)计算图中出度为0的顶点个数。返回5.已知一个有n个顶点的有向图的邻接表，设计算法分别实现返126