《图的定义和术语》PPT课件.ppt

《《图的定义和术语》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图的定义和术语》PPT课件.ppt（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章 图6.1 图的定义和术语6.2 图的存储结构6.3 图的遍历6.4 最小生成树6.5 最短路径6.6 拓扑排序6.7 典型题例6.8 实训例题6.1 6.1 图的定义和术语图的定义和术语611 图的定义图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空穷集合有穷集合 E(G)是用顶点对表示的边（Edge）的有穷集合，可以为空。无向图若图G中表示边的顶点对是无序的（称无向边），则称图G为无向图。通常用(vi，vj)表示顶点vi和vj间的无向边。有向图若图G中表示边的顶点对是有序的（称有向边），则称图G为有向图。通常用表示从顶点vi到顶点

2、vj的有向边，有向边也称为弧，顶点vi称为弧尾（或初始点），顶点vj称为弧头（或终端点），用由弧尾指向弧头的箭头形象地表示弧。例如图6.1所示，G1是无向图，其中，V=v0，v1，v2，v3，v4，E=(v0，v1)，(v0，v3)，(v0，v4)，(v1，v4)，(v1，v2)，(v2，v4)，(v3，v4)；G2是有向图，其中，V=v0，v1，v2，v3，E=，。(a)图 G1(b)图 G2图6.1 图的示例v4v3v0v3v0v1v2v1v26.1.2 图的基本术语邻接点在无向图G(V，E)中，若边(vi，vj)E，则称顶点vi和vj互为邻接点（Adjacent），或vi和vj相邻接，并

3、称边(vi，vj)与顶点vi和vj相关联，或者说边(vi，vj)依附于顶点vi，vj。在有向图G（V，E）中，若弧E，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，并称弧和顶点vi，vj相关联。顶点的度、入度和出度顶点vi的度（Degree）是图中与vi相关联的边的数目，记为TD(vi)。对于有向图，顶点vi的度等于该顶点的入度和出度之和，即TD（vi）ID（vi）OD（vi）。其中，顶点vi的入度（InDegree）ID（vi），是以vi为弧头的弧的数目；顶点vi的出度（OutDegree）OD（vi）是以vi为弧尾的弧的数目。完全图、稠密图、稀疏图若无向图中有n(n 1)条边，即图中

4、每对顶点之间都有一条边，则称该无向图为无向完全图。若有向图中有n(n 1)条弧，即图中每对顶点之间都有方向相反的两条弧，则称该有向图为有向完全图。有很少条边或弧（enlogn）的图称为稀疏图，反之称为稠密图。v3v0v1v2v0v1v2(a)无向完全图G3(b)有向完全图 G4图6.2完全图子图：假设有两个图G（V，E），G（V，E），若有VV，EE，则称图G是图G的子图。路径：无向图G（V，E）中，从顶点v到顶点v间的路径（path）是一个顶点序列（v=vi0，vi1，vim=v），其中（vij 1，vij）E，jm；若G是有向图，则路径也是有向的，且vij 1，vijE，jm。路径上边或弧

5、的数目称为路径长度。如果路径的起点和终点相同（即vv），则称此路径为回路或环（Cycle）。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。(a)图6.1 中G1的子图v0v4v0v1v2v4v3v0v1v0v1v0v3v0v1v2(b)图6.1中G2的子图图6.3 子图示例连通图、连通分量：在无向图G中，若从顶点vi到顶点vj(ij)有路径相通，则称vi和vj是连通的。如果图中任意两个顶点vi和vj(ij)都是连通的，则称该图是连通图（Connected Graph）。无向图中极大连通子图称为连通分量（Connecte

6、d Component）。强连通图、强连通分量：在有向图中，若任意两个顶点vi和vj都连通，即从vi到vj和从vj到vi 都有路径相通，则称该有向图为强连通图，例如图6.2 中G4就是强连通图。有向图中的极大强连通子图称为该有向图的强连通分量。v5图6.4无向图及其连通分量v4v3v0v1v2(a)无向图 G5v7v6(b)G5的三个连通分量v4v3v0v1v2v5v7v6v3v0v1v2图6.5有向图G2的两个强连通分量(a)(b)权、网：图的每条边或弧上常常附上一个具有一定意义的数值，这种与边或弧相关的数值称为该边（弧）的权（Weight）。边或弧上带权的连通图称为网（Network）。如

7、图6.6所示。10706030205090图6.6 网G6示例v1v4v0v2v36 62 2 图的存储结构图的存储结构621 邻接矩阵1邻接矩阵这种存储结构采用两个数组来表示图：一个是一维数组，存储图中的所有顶点的信息；另一个是二维数组即邻接矩阵，存储顶点之间的关系。设G=（V，E）是具有n个顶点的图，顶点序号依次为0，1，n-1，即V(G)=v0，v1，vn-1，则图G的邻接矩阵是具有如下性质的n阶方阵：Aij=1 若（vi，vj）或E0 反之图6.7 无向图G1、有向图G2的邻接矩阵0 1 0 1 11 0 1 0 10 1 0 0 11 0 0 0 11 1 1 1 0A10 1 0

8、0 0 0 1 0 1 0 0 0 0 0 1 0 A2(a)G1的邻接矩阵(b)G2的邻接矩阵若G是网，则其邻接矩阵是具有如下性质的n阶方阵：Wij 若（vi，vj）或E Aij=反之这里，Wij表示边(vi，vj)或弧上的权值；代表一个计算机内允许的、大于所有边（弧）上权值的正整数。30 60 2030 10 90 10 50 60 50 7020 90 70 A=类型描述:#define MaxSize 顶点数目typedef struct VexType vexsMaxSize;/*顶点数组*/int arcsMaxSize MaxSize;/*邻接矩阵*/int vexnum,arc

9、num;/*顶点数，边（弧）数*/AdjMatrix;特点:无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度TD（vi）；对于有向图，邻接矩阵的第i行非零元素的个数正好是第i个顶点的出度OD（vi），第i列非零元素的个数正好是第i个顶点的入度ID（vi）。对于无向图，图中边的数目是矩阵中1的个数的一半；对于有向图，图中弧的数目是矩阵中1的个数；从邻接矩阵很容易确定图中任意两个顶点间是否有边（或弧）相连，第i行j列的值为1表示顶点i和顶点j之间有边相连。2建立图的邻接矩阵建立图的邻接矩阵 假设顶点数组中存放的顶

10、点信息是字符类型，即VexType为char类型。首先输入顶点的个数、边的条数，由顶点的序号建立顶点表（数组）。然后将矩阵的每个元素都初始化成0，读入边(i，j)，将邻接矩阵的相应元素的值(第i行第j列和第j行第i列)置为1。算法描述如下 typedef char VexType void CreatAMgraph(AdjMatrix *g)/*建立无向图的邻接矩阵g*/printf(“please input vexnum and arcnum:n”);scanf(“%d”,&g-vexnum);scanf(“%d”,&g-arcnum);getchar();/*吃掉输入的换行符*/for(

11、i=0;ivexnum;+i)printf(“please input vexs:n”);scanf(“%c”,&g-vexsi);/*建立顶点数组*/for(i=0;ivexnum;+i)/*初始化邻接距阵*/for(j=0;jvexnum;+j)g-arcsij=0;for(k=0;karcnum;k+)printf(“please input edges:n”);scanf(“%d,%d”,&i,&j);/*输入边（i，j）,i，j为顶点序号*/g-arcsij=1;g-arcsji=1;/*CreatAMgraph*/其执行时间是O（n+n2+e），其中O（n2）的时间耗费在邻接矩阵的

12、初始化操作上。因为evexnum，&g-arcnum)；/*读人顶点数和边数*/getchar();for(i=0；ivexnum；i+)/*建立表头结点表*/printf(“please input%d vertex:n”,i);scanf(“%c”,&g-vertexi.data)；/*读入顶点信息*/g-vertexi.firstarc=NULL；/*边表置为空表*/for(k=0；karcnum；k+)/*建立边表*/printf(“please input edges:n”);scanf(dd，&i,&j)；/*读入边(vi，vj)的顶点对序号*/s=(ArcNode*)malloc

13、(sizeof(ArcNode)；/*生成边表结点*/s-adjvex=j;/*邻接点序号为j*/s-nextarc=g-vertexi.firstarc；/*将新结点*s插入顶点vi的边表头部*/g-vertexi.firstarc=s；s=(ArcNode*)malloc(sizeof(ArcNode)；s-adjvex=i;/*邻接点序号为i*/s-nextarc=g-vertexj.firstarc；/*将新结点*s插入顶点vj的边表头部*/g-vertexj.firstarc=s；/*CreateALGraph*/在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表

14、的时间复杂度为O(n+e)，否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为O(n*e)。注意：从逻辑上说，一个顶点的所有邻接点之间并没有先后之分，但当图的具体的存储结构建立后，一个顶点的所有邻接点之间就可以分出先后。（1）邻接矩阵是一种静态的存储结构；邻接表是一种动态的存储结构。（2）邻接矩阵是顺序存储结构，因此相应的算法实现较简单；邻接表中有指针，因此相应的算法较为复杂。（3）邻接矩阵占用的存储单元数目只与图中顶点个数有关，而与边（弧）的数目无关，对于一个具有n个顶点e条边的图G，其邻接矩阵所占存储单元为n2，而其邻接表（和逆邻接表）中有n个表头结点和2e个边（弧）结点；在稀疏图中

15、边的数目远远小于n2（即en2），这时用邻接表比用邻接矩阵节省存储空间；若是稠密图，因邻接表中要附加链域，则选取邻接矩阵更合适。（4）在邻接矩阵中，很容易判定任意两个顶点vi，vj之间是否有边或弧相连，只要判定矩阵中的第i行第j列上的元素的值即可；但是在邻接表中，需搜索第i个或第j个边表，最坏情况下要耗费O（n）时间。(5）在邻接矩阵中求边的数目e，必须检测整个矩阵，所耗费的时间是O（n2），与e的大小无关；而在邻接表中，只要对每个边表的结点个数计数即可求得e，所耗费的时间是O（e+n）。因此，当evexsi);/*访问顶点vi*/visitedi=1;for(j=0;jvexnum;j+)i

16、f(g-arcsij=1)&(!visitedj)DFS1(g,j);/*DFS1*/以邻接表作为图的存储结构的深度优先搜索遍历算法描述如下：int visited MaxSize=0;void DFS2(AdjList *g,int i)/*从第i个顶点出发深度优先遍历图G，G以邻接表表示*/printf(“%3c”,g-vertexi.data);/*访问顶点vi*/visitedi=1;for(p=g-vertexi.firstarc;p;p=p-nextarc)if(!visitedp-adjvex)DFS2(g,p-adjvex);/*DFS2*/算法分析：分析DFS算法得知，遍历图

17、的过程实质上是对每个顶点搜索其邻接点的过程。耗费的时间取决于所采用的存储结构。假设图中有n个顶点，那么，当用邻接矩阵表示图时，搜索一个顶点的所有邻接点需花费的时间为O（n），则从n个顶点出发搜索的时间应为O（n2）,所以算法DFS1的时间复杂度是O（n2）；如果使用邻接表作为图的存储结构时，搜索一个顶点的所有邻接点需花费的时间为O（e），其中e为无向图中边的数目或有向图中弧的数目，则算法DFS2的时间复杂度为O(n+e)。6.3.2 连通图的广度优先搜索 基本思想:从图中某个顶点vi出发，在访问了vi之后，依次访问vi的各个未曾访问过的邻接点；然后分别从这些邻接点出发，依次访问它们的未曾访问过

18、的邻接点，直至所有和起始顶点vi有路径相通的顶点都被访问过为止。以图6.11(a)中图G为例说明广度优先搜索的过程顶点访问序列为：v0v1v2v3v4v5v6v7。(4)(3)(7)(5)(6)(2)(1)v0v2v1v3v4v5v6v7图 6.12 图的广度优先搜索过程 以邻接矩阵作为图的存储结构的广度优先搜索遍历算法描述如下：int visitedMaxSize=0;void BFS1(AdjMatrix g,int i)/*从第i个顶点出发广度优先遍历图G，G以邻接矩阵表示*/int k;Queue Q;/*定义一个队列*/printf(“%3c”,g.vexsi);/*访问顶点vi*/

19、visitedi=1;InitQueue(&Q);/*置空队列Q*/EnQueue(&Q,i);/*vi入队列*/while (!Empty(Q)DeQueue(&Q,&k);/*队头顶点出队列*/for(j=0;jadjvex)printf(“%3c”,g.vertexp-adjvex);/*访问顶点k的未曾访问的顶点*/visitedp-adjvex=1;EnQueue(&Q,p-adjvex);p=p-nextarc;/*求k的下一个邻接点*/*BFS2*/算法分析：分析上述算法，每个顶点至多进一次队列，所以算法中的内、外循环次数均为n次，故算法 BFS1的时间复杂度为O（n2）；若采用

20、邻接表存储结构，广度优先搜索遍历图的时间复杂度与深度优先搜索是相同的。6.3.3 非连通图的遍历 如果给定的图是不连通的，则调用上述遍历算法（深度或广度优先搜索算法）只能访问到起始顶点所在的连通分量中的所有结点，其它连通分量中的结点是访问不到的。为此，需从每一个连通分量中选取起始顶点，分别进行遍历，才能访问到图中的所有顶点。深度优先搜索遍历非连通图的算法描述如下：void DFSUnG(AdjMatrix*g)int i for(i=0;ivexnum;i+)if visitedi=0)DFS(g,i);6.4 6.4 最小生成树最小生成树641 生成树及最小生成树1生成树一个连通图的生成树是

21、是一个极小连通子图，它含有图中全部顶点，但是一个极小连通子图，它含有图中全部顶点，但只有只有n-1条边。条边。一个连通图的生成树是不惟一的。由深度优先搜索得到的生成树称为深度优先生成树；由广度优先搜索得到的生成树称为广度优先生成树。（a）深度优先生成树（b）广度优先生成树图6.13 图的生成树v3v2v1v0v6v5v4v7v2v1v0v6v5v4v3v72最小生成树 在一个连通网的所有生成树中，各边的权值之和最小的那棵生成树称为该连通网的最小代价生成树（Minimum Cost Spanning Tree），简称为最小生成树。构造最小生成树的算法很多，其中多数算法都利用了最小生成树的一种称之

22、为MST的性质。MST性质：假设 G=（V，E）是一连通网，U 是顶点集V的一个非空子集。若（u，v）是一条具有最小权值的边，其中uU，vV-U，则必存在一棵包含边（u，v）的最小生成树。常用的构造最小生成树的算法有普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。6.4.2 6.4.2 普里姆算法普里姆算法 1算法的思想 假设G（V，E）是一个连通网，U是最小生成树中的顶点的集合，TE是最小生成树中边的集合。初始令U=u1（u1V）,TE=，重复执行下述操作：在所有uU，vW=V-U的边(u，v)E中选择一条权值最小的边(u，v)并入集合TE，同时将u并入U中，直至U=V为止。此时T

23、E中必有n-1条边，则T=(U，TE)便是G的一棵最小生成树。普利姆算法逐步增加集合U中的顶点，直至U=V为止。1010861271012610155图6.14普里姆算法构造最小生成树的过程v3v4v0v1v2v5v0v4v0(a)(b)(c)(d)(e)(f)(g)5v3v4v0105v3v4v0v2105v3v4v0v2v57105v3v4v0v1v2v57106662算法的实现 为了实现普里姆算法，需要附设一个辅助数组closedge，以记录从U到VU的具有最小权值的边。其数据类型定义如下：struct closedge VexType adjvex;int lowcost;closed

24、geMaxSize;对于每个顶点viVU，在辅助数组closedge 中存在一个分量closedgei，其中closedgei.lowcost存储所有与vi邻接的、从U到VU的那组边中的最小边上的权值，显然有closedgei.lowcostMincost(u,vi)|uU，其中cost(u,vi)表示边(u,vi)的权值。一旦顶点vi并入U，则closedgei.lowcost置为零；而closedgei.adjvex存储依附于该边的U中的顶点。图6.15展示了在图6.14所示的构造最小生成树的过程中，辅助数组closedge中各分量值的变化情况。P161算法描述如下：int LocatVe

25、x(AdjMatrix g,VexType u0);int Mininum(struct closedge closedge,int vexnum);void Prim(AdjMatrix g,VexType u0)/*从顶点u0出发构造网G的最小生成树T，输出T中的每条边*k=LocatVex(g,u0);*确定顶点u0在网G中的序号*closedgek.lowcost=0;for(j=0;jg.vexnum;j+)/*初始化辅助数组*if(j!=k)closedgej.adjvex=u0;closedgej.lowcost=g.arcskj;closedgek.lowcost=0;/*初始

26、U=u0*/for(i=1;i=g.vexnum-1;i+)k=Mininum(closedge,g.vexnum);/*求权值最小的顶点的序号，vk*/printf(“(%c,%c),%d ”,closedgek.adjvex,g.vexsk,closedgek.lowcost);/*输出生成树T的边及权值*closedgek.lowcost=0;/*顶点vk并入U*/for(j=0;jg.vexnum;j+)/*重新调整closedge*/if(g.arcskjclosedgej.lowcost)closedgej.lowcost=g.arcskj;closedgej.adjvex=g.v

27、exsk;/*if*/*for*/*Prim*/int LocatVex(AdjMatrix g,VexType u0)/*返回顶点u0在网G中的序号*for(i=0;ig.vexnum;i+)if(g.vexsi=u0)return(i);/*LocatVex*/int Mininum(struct closedge closedge,int vexnum)/*在辅助数组closedge中求出权值最小的边的顶点序号min,且vminV-U*/for(i=0;ivexnum;i+)if(closedgei.lowcost!=0)break;min=i;for(i=0;ivexnum;i+)if

28、(closedgei.lowcost!=0&closedgei.lowcost closedgemin.lowcost)min=i;return(min);/*Mininum*/假设网中有n个顶点，普里姆算法中有两个循环，所以时间复杂度为（n），它与网中边的数目无关，因此普里姆算法适合于求边稠密的网的最小生成树。643 克鲁斯卡尔算法 基本思想:按权值递增的次序来选择合适的边构成最小生成树。假设G（V，E）是连通网，最小生成树T（V，TE）。初始时，TE，即T仅包含网G的全部顶点，没有一条边，T中每个顶点自成一个连通分量。算法执行如下操作：在图G的边集E中按权值递增次序依次选择边（u,v），若

29、该边依附的顶点u,v分别是当前的两个连通分量中的顶点，则将该边加入到TE中；若u,v是当前同一个连通分量中的顶点，则舍去此边而选择下一条权值最小的边。依此类推直到T中所有顶点都在同一连通分量上为止，此时T便是G的一棵最小生成树。与普里姆算法不同，克鲁斯卡尔算法是逐步增加生成树的边。克鲁斯卡尔算法可描述如下：T=(V,);While(T中的边数en-1)从E中选取当前权值最小的边（u,v）；if(u,v)并入T之后不产生回路)将边（u,v）并入T中；else 从E中删去边（u,v）；可以证明克鲁斯卡尔算法的时间复杂度是（eloge），其中e是网G的边的数目。克鲁斯卡尔算法适合于求边稀疏的网的最小

30、生成树。现以图6.14(a)所示的网为例，按克鲁斯卡尔算法构造最小生成树。其构造过程如图6.16所示。5567561075610106图6.16 kruskal算法构造最小生成树的过程v3v4v0v1v2v5(a)v3v4v0v1v2v5v3v4v0v1v2v5v3v4v0v1v2v5v3v4v0v1v2v5(d)(c)(b)(e)7565 最短路径 问题提出用带权的有向图表示一个地区的交通运输网，图中：顶点表示城市边上的权 表示城市间的公路权表示两个城市间的距离，或者表示通过这段公路所需的时间或需要花费的代价等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路

31、径最短路径从某个源点到其余各顶点的最短路径1367172853230v1v5v0v2v4v69(a)有向网络v3最短路径 长度813 19 21 13 20(b)从源点v0到其余各顶点的最短路径和长度图6.17有向网络及从源点到其余各顶点的最短路径和长度迪杰斯特拉(Dijkstra)算法按路径长度递增的次序产生最短路径的算法 基本思想：把V分成两组：S：已求出最短路径的顶点的集合,V-S=T：尚未确定最短路径的顶点集合初始时，S中只包含源点v0，T中包含除源点外的其余顶点，此时各顶点的当前最短路径长度为源点到该顶点的弧上的权值，然后按最短路径长度递增的次序逐个把T中的顶点加到S中去，直至从v0

32、出发可以到达的所有顶点都包括到S中为止。保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度 设有向图G有n个顶点（v0为源点），其存储结构用邻接矩阵表示。算法实现时需要设置三个数组sn、distn和pathn。s用以标记那些已经找到最短路径的顶点集合S，若si=1,则表示已经找到源点到顶点vi的最短路径，若si=0，则表示从源点到顶点vi的最短路径尚未求得，数组的初态为：s0=1，si=0,i=1,2,n-1，表示集合S

33、中只包含一个顶点v0。数组dist记录源点到其他各顶点的当前的最短距离，其初值为：disti=g.arcs0i i=1,2,n-1 path是最短路径的路径数组，其中pathi表示从源点v0到顶点vi之间的最短路径上该顶点的前驱顶点，若从源点到顶点vi无路径，则pathi=-1。求最短路径步骤初使时令 S=V0,T=其余顶点，T中顶点对应的距离值若存在，为弧上的权值若不存在，为从T中选取一个其距离值为最小的顶点W，加入S，即令sw=1；对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值，即从原来的distj和distw+g.arcswj中选择

34、较小的值作为新的distj。重复上述步骤，直到S中包含所有顶点，即S=V为止网采用邻接矩阵做存储结构，用迪杰斯特拉算法求最短路径的算法描述如下：void Dijkstra(AdjMatrix g,int v0,int path,int dist)/*求有向网g的从顶点v0到其余顶点v的最短路径，pathv是v0到v的最短路径上v的前驱顶点，distv是路径长度*int sMaxSize,v;for(v=0;vg.vexnum;v+)*初始化s、dist 和path 三个数组*sv=0;distv=g.arcsv0v;if(distvMAXINT&v!=v0)pathv=v0;/*MAXINT

35、为int类型的最大值*/else pathv=-1；distv0=0;sv0=1;*初始时源点v0S集*循环求v0到某个顶点v的最短路径，并将v加入S集*for(i=0;i g.vexnum-1;i+)min=MAXINT;/*MAXINT是一个足够大的数*/v=-1;/*v记录找到的最小距离的顶点序号*/for(w=0;wg.vexnum;w+)if(!sw&distwmin)*顶点w不属于S且离v0更近*v=w;min=distw;if(v!=-1)/*找到最小距离的顶点v*/sv=1;*顶点v并入S*for(j=0;jg.vexnum;j+)*更新当前最短路径及距离*if(!sj&(mi

36、n+g.arcsvjdistj)distj=min+g.arcsvj;pathj=v;/*if*/*if*/*for*/*Dijkstra*/通过pathi向前推导直到v0为止，可以找出从v0到顶点vi的最短路径。例如，对于图6.17(a)的有向网络，按上述算法计算出的path数组的值为：求顶点v0到顶点v3的最短路径的计算过程为：path3=2,说明路径上顶点v3之前的顶点是顶点v2；path2=1,说明路径上顶点v2之前的顶点是顶点v1；path1=0,说明路径上顶点v1之前的顶点是顶点v0。则顶点v0到顶点v3的路径为v0，v1，v2，v3。迪杰斯特拉算法中有两个循环次数为顶点个数n的嵌

37、套循环，所以其时间复杂度为（n2）。0123456-1012305输出最短路径的算法描述如下：void PrintPath(int v0,int p,int d,int vexnum)*输出源点v0到其余顶点的最短路径和路径长度,路径逆序输出*for(i=0;ivexnum;i+)if(diMAXINT&i!=v0)printf(“v%d-“,i);next=pi;while(next!=v0)printf(“v%d-“,next);next=pnext;/*while*/printf(“v%d：%dn”,v0,di);else if(i!=v0)printf(“v%d-v%d:nopathn

38、”,i,v0);/*PrintPath*/对于图6.17(a)的有向网络，其邻接矩阵如图6.18(a)所示，利用Dijkstra算法计算从顶点v0到其他各顶点的最短路径的动态执行情况如图6.18(b）所示。P166,最后的输出结果是：v-v0:8v2-v1-v0:13v3-v2-v1-v0:19v4-v3-v2-v1-v0:21v5-v0：13v6-v5-v0:20 给出一个含有n个顶点的带权有向图，求其每一对顶点之间的最短路径。解决这个问题的一种方法是：每次以一个顶点为源点，执行迪杰斯特拉算法，求得从该顶点到其他各顶点的最短路径；重复执行n次之后，就能求得从每一个顶点出发到其他各顶点的最短路

39、径。66 拓扑排序问题提出：学生选修课程问题 顶点表示课程 有向弧表示先决条件，若课程i是课程j的先决条件，则图中有弧 学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序定义 AOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网 若是网中的一条弧，则称顶点i优先于顶点j，i是j的直接前驱，或称j是i的直接后继。一个顶点如果没有前驱，则该顶点所表示的子工程可独立于整个工程，即该子工程的开工不受其他子工程的约束。否则，一个子工程的开工必须以其前驱所代表的子工程的完工为前提条件。AOV网中不允

40、许有回路，这意味着某项活动以自己为先决条件 拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫 检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环 对AOV网进行拓扑排序的方法和步骤是：(1)在有向图中选一个没有前驱（即入度为0）的顶点并且输出之。(2)从图中删去该顶点和所有以该顶点为弧尾的弧。重复上述两步，直至全部顶点均被输出，或者当前网中不再存在没有前驱的顶点为止。操作结果的前一种情况说明网中不存在有向回路，拓扑排序成功；后一种情况说明网中存在有向回路。图6.20给出了一个按上述步骤求

41、AOV网的拓扑序列的例子。这样得到的一个拓扑排序序列为：v0，v4，v1，v2，v5，v3。v4v1v0图6.20 AOV网及其拓扑有序序列的产生过程v2v3v5(a)AOV网(b)输出v0后v3v5(e)输出v2后后后v3(f)输出v5后后后(c)输出v4后后后v2v3v5(d)输出v1后后后v4v1v2v3v5v1v2v3v5拓扑排序算法的实现 用邻接表作为有向图的存储结构，并且在表头结点中增设一个入度域（indegree），存放顶点的入度。每个顶点的入度域的值随邻接表动态生成过程累计得到。例如图6.21所示为图6.20(a)的AOV网的邻接表。入度为0的顶点即为没有前驱的顶点，删除顶点及

42、以它为弧尾的弧的操作，则可转换为将它的所有弧头顶点的入度域减来实现。为了避免重复检测入度为零的顶点，可另设一个栈来暂时存放所有入度为零的顶点。拓扑排序算法可形式地描述如下：(1)扫描顶点表，将入度为零的顶点入栈；(2)while(栈非空)将栈顶顶点vj弹出并输出之；在邻接表中查vj的直接后继vk，把vk的入度减，若vk的入度为零则进栈；(3)若输出的顶点数小于n,则表示有回路；否则拓扑排序正常结束。算法中的邻接表的结构描述如下。#define MaxSize 顶点数目typedef struct ArcNode int adjvex;/*邻接点序号*/struct ArcNode *nexta

43、rc;otherinfo info;ArcNode;/*边结点*/typedef struct VertexNode VertexType data;int indegree;/*入度*/ArcNode*firstarc;VertexNode;/*表头结点*/typedef struct VertexNode vertexMaxSize;int vexnum,arcnum;AdjList;/*图的邻接表*/算法的具体描述如下：void TopSort(AdjList *g)/*top为栈顶指针，n统计输出顶点数，s为栈*/int top,n,k,j,sMaxSize;ArcNode*q;top

44、=-1;n=0;for(j=0;jvexnum;j+)/*入度为0的顶点进栈*/if(g-vertexj.indegree=0)s+top=j;while(top!=-1)/*拓扑排序*/j=stop-;/*出栈*/printf(%c ,g-vertexj.data);/*输出顶点*/n+;q=g-vertexj.firstarc;/*找第一个邻接点*/while(q!=NULL)k=q-adjvex;g-vertexk.indegree-;if(g-vertexk.indegree=0)/*入度为0的邻接点入栈*/s+top=k;q=q-nextarc;/*找下一个邻接点*/*while*/

45、*while*/printf(nn=%dn,n);if(nvexnum)printf(The network has a cyclen);/*TopSort*/算法分析：O(n+e)。67 典型题例【例1】已知一个无向图的邻接表如图6.22所示，要求：（1）画出该无向图；（2）根据邻接表，分别写出按DFS和BFS算法从顶点v0开始遍历的遍历序列，并画出DFS生成树和BFS生成树。6v60123图6.22 一个图的邻接表表示:6v60123图6.22 一个图的邻接表表示45v0v1v2v3v4v51325613042036112406250（1）该无向图如图6.23(a)所示。（2）根据该无向图

46、的邻接表表示，从顶点v0开始的深度优先遍历的序列为：v0v2v3v1v4v6v5，其相应的生成树如图6.23(b)所示；从顶点v0开始的广度优先遍历的序列为：v0v2v5v6v1v3v4，其相应的生成树如图6.23(c)所示。v0v2v6图6.23 无向图及其生成树v3v4(a)无向图v1v5v0v2v3v6v5v1v4v0v2v5v6v1v3v4(b)DFS生成树(c)BFS生成树【例2】以邻接表为存储结构，利用DFS搜索策略设计一个算法，求图中从顶点u到顶点v的一条简单路径，并输出该路径。从顶点u开始，进行深度优先搜索，如果能够搜索到顶点v，则表明从顶点u到顶点v有一条路径。由于在搜索过程

47、中每个顶点只访问一次，所以这条路径一定是简单路径。因此，只要在搜索过程中把当前的搜索线路记录下来，并在搜索到顶点v时退出搜索过程，就可以得到从u到v的一条简单路径。为了记录当前的搜索路线，设立一个数组pathn，当从某个顶点vi找到其邻接点vj进行访问时，将pathi置为j，即pathi=j。这样，当退出搜索后，输出path数组，就可以得到从u到v的简单路径。算法描述如下：int pathMaxSize;int visitedMaxSize,found;/*found为是否找到路径标志*/void SimplePath(AdjList*g,int u,int v)/*找一条从u到v的简单路径*

48、/for(i=0;ivexnum;i+)visitedi=0;found=0;DFSPath(g,u,v);/*利用深度优先搜索找一条从u到v的简单路径*/*SimplePath*void DFSPath(Adjlist*g,int u,int v)ArcNode*q;if(found)return;visitedu=1;for(q=g-vertexu.firstarc;q;q=q-nextarc)if(q-adjvex=v)pathu=v;found=1;PrintPath(u,v);/*输出路径*/else if(!visitedq-adjvex)pathu=q-adjvex;DFSPat

49、h(g,q-adjvex,v);/*DFSPath*/void PrintPath(int u,int v)printf(“%d”,u);for(k=pathu;k!=v;k=pathk)printf(“%d”,k);printf(“%d”,v);/*PrintPath*/6 68 8 实训例题实训例题实训例题实训例题1 设计学习计划设计学习计划【问题描述】软件专业的学生要学习一系列课程，其中有些课程在其先修课程完成后才能学习，如6.6节图6.19所示。假设每门课程的学习时间为一学期，试为该专业的学生设计学习计划，使他们能够在最短的时间内修完这些课程。【基本要求】功能：为学生设计学习计划。输入

50、：输入学生需要学习的课程之间的先修关系。即把课程之间的先修关系表示为AOV网，输入该网。输出：学生学习课程的计划，即输入的AOV网的拓扑序列。【数据结构】采用AOV网表示课程之间的先修关系，因为在算法中要涉及求顶点的邻接点，所以存储结构采用邻接表比较合适。其类型描述为：typedef int VertexType;/*为简单起见，顶点信息设为顶点序号*/typedef struct ArcNode int adjvex;/*邻接点序号*/struct ArcNode *nextarc;otherinfo info;ArcNode;/*边结点*/typedef struct VertexNode