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

《《图的定义和术语》PPT课件》由会员分享，可在线阅读，更多相关《《图的定义和术语》PPT课件（91页珍藏版）》请在装配图网上搜索。

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

2、，有向边也称为弧，顶点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 图 的 示 例v4 v3v0 v3v0v1 v2v1 v2 6.1.2 图的基本术语邻接点在无向图G(V，E)中，若边(vi，vj) E，则称顶点vi和vj互为邻接点（Adjacent），或

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

4、n(n 1)条边，即图中每对顶点之间都有一条边，则称该无向图为无向完全图。若有向图中有n( n 1)条弧，即图中每对顶点之间都有方向相反的两条弧，则称该有向图为有向完全图。有很少条边或弧（enlogn）的图称为稀疏图，反之称为稠密图。 v 3v0v1 v2 v0v1 v2(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；

5、若G是有向图，则路径也是有向的，且vij 1 ，vij E，jm。路径上边或弧的数目称为路径长度。如果路径的起点和终点相同（即vv），则称此路径为回路或环（Cycle）。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。(a) 图 6.1 中 G1的 子 图v0 v4v0v1 v2 v4 v3v0v1v0v1v0 v3v0v1 v2(b) 图 6.1中 G2的 子 图图 6.3 子 图 示 例 连通图、连通分量：在无向图G中，若从顶点vi到顶点vj(ij)有路径相通，则称vi和vj是连通的。如果图中任意两个顶点vi和vj(

6、ij)都是连通的，则称该图是连通图（Connected Graph）。无向图中极大连通子图称为连通分量（Connected Component ）。强连通图、强连通分量：在有向图中，若任意两个顶点vi和vj都连通，即从vi到vj和从vj到vi 都有路径相通，则称该有向图为强连通图，例如图6.2 中G4就是强连通图。有向图中的极大强连通子图称为该有向图的强连通分量。 v5 图 6.4无 向 图 及 其 连 通 分量v4v3v0v1 v2(a) 无 向 图 G5v7v6 (b) G5的 三 个 连 通分 量 v4v3v0v1 v2 v5 v7 v6 v3v0v1 v2图 6.5有 向 图 G2的

7、两 个 强 连 通 分量(a) (b) 权、网：图的每条边或弧上常常附上一个具有一定意义的数值，这种与边或弧相关的数值称为该边（弧）的权（Weight）。边或弧上带权的连通图称为网（Network）。如图6.6所示。 10 706030 205090图 6.6 网 G6示 例v1 v4v0v2 v3 62 图的存储结构621 邻接矩阵1邻接矩阵这种存储结构采用两个数组来表示图：一个是一维数组，存储图中的所有顶点的信息；另一个是二维数组即邻接矩阵，存储顶点之间的关系。 设G=（V，E）是具有n个顶点的图，顶点序号依次为0，1，n-1，即V(G)=v0，v1，vn-1，则图G的邻接矩阵是具有如下性

8、质的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 0A1 0 1 0 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)或弧上的权值；代表一个计算机内允许的、大于所有边（弧）上权值的正整数。例如图6.6所示网G6的邻接矩阵如图6

9、.8所示 30 60 2030 10 90 10 50 60 50 7020 90 70 A= 类型描述 :#define MaxSize 顶点数目typedef struct VexType vexsMaxSize; /*顶点数组*/int arcsMaxSize MaxSize; /*邻接矩阵*/int vexnum,arcnum; /*顶点数，边（弧）数*/AdjMatrix; 特点 :无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。 对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度TD（vi）；对于有向图，邻接矩阵的第i行非零元素的个数正好是第i个

10、顶点的出度OD（vi），第i列非零元素的个数正好是第i个顶点的入度ID（vi）。对于无向图，图中边的数目是矩阵中1的个数的一半；对于有向图，图中弧的数目是矩阵中1的个数；从邻接矩阵很容易确定图中任意两个顶点间是否有边（或弧）相连，第i行j列的值为1表示顶点i和顶点j之间有边相连。 2建立图的邻接矩阵 假设顶点数组中存放的顶点信息是字符类型，即VexType为char类型。 首先输入顶点的个数、边的条数，由顶点的序号建立顶点表（数组）。然后将矩阵的每个元素都初始化成0，读入边(i，j)，将邻接矩阵的相应元素的值(第i行第j列和第j行第i列)置为1。 算法描述如下 typedef char Vex

11、Type void CreatAMgraph(AdjMatrix *g) /*建立无向图的邻接矩阵g*/ printf(“please input vexnum and arcnum:n”); scanf(“%d”, scanf(“%d”, getchar( ); /*吃掉输入的换行符*/ for (i=0;ivexnum;+i) printf(“please input vexs:n”); scanf(“%c”, /*建立顶点数组*/ for (i=0;ivexnum;+i) /*初始化邻接距阵*/ for (j=0;jvexnum;+j) g-arcsij=0; for (k=0;karc

12、num;k+) printf(“please input edges:n”); scanf(“%d,%d”, /*输入边（i，j）,i，j为顶点序号*/ g-arcsij=1; g-arcsji=1; /*CreatAMgraph*/ 其执行时间是O（n+n2+e），其中O（n2 ）的时间耗费在邻接矩阵的初始化操作上。因为evexnum， for(i=0；ivexnum；i+)/*建立表头结点表*/ printf(“please input %d vertex:n”,i); scanf(“%c”, scanf(dd， /*邻接点序号为j*/ s-nextarc=g-vertexi.firsta

13、rc； /*将新结点*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 */ 在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表的时间复杂度为O(n+e)，否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为O(n*e)。 注意：从逻辑上说，一个顶

14、点的所有邻接点之间并没有先后之分，但当图的具体的存储结构建立后，一个顶点的所有邻接点之间就可以分出先后。 6.2.3邻接矩阵和邻接表的比较 （1）邻接矩阵是一种静态的存储结构；邻接表是一种动态的存储结构。（2）邻接矩阵是顺序存储结构，因此相应的算法实现较简单；邻接表中有指针，因此相应的算法较为复杂。（3）邻接矩阵占用的存储单元数目只与图中顶点个数有关，而与边（弧）的数目无关，对于一个具有n个顶点e条边的图G，其邻接矩阵所占存储单元为n2，而其邻接表（和逆邻接表）中有n个表头结点和2e个边（弧）结点；在稀疏图中边的数目远远小于n2（即en2），这时用邻接表比用邻接矩阵节省存储空间；若是稠密图，因

15、邻接表中要附加链域，则选取邻接矩阵更合适。 （4）在邻接矩阵中，很容易判定任意两个顶点v i，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+) if (g-arcsij=1)/*DFS1*/ 以邻接表作为图的存储结构

16、的深度优先搜索遍历算法描述如下：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的各个未曾访问过的邻接点；然后分别从这些邻接点出发，依次访问它们的未曾访问过的邻接点，直至所有和起始顶点vi有路径相通的顶点都被访问过为止。 以图6.11(

18、a)中图G为例说明广度优先搜索的过程顶点访问序列为： v 0v1v2v3v4v5v6v7。 (4)(3) (7) (5) (6)(2)(1) v0 v2v1v3 v4 v5 v6v7图 6.12 图 的 广 度 优 先 搜 索 过 程 以邻接矩阵作为图的存储结构的广度优先搜索遍历算法描述如下：int visitedMaxSize=0;void BFS1(AdjMatrix g,int i)/*从第i个顶点出发广度优先遍历图G，G以邻接矩阵表示*/ int k; Queue Q; /*定义一个队列*/ printf(“%3c”,g.vexsi); /*访问顶点v i */ visitedi=1;

19、 InitQueue( /*置空队列Q */ EnQueue( /* vi入队列 */ while (!Empty(Q) DeQueue( /*队头顶点出队列 */ for (j=0;jadjvex) printf(“%3c”, g.vertexp-adjvex); /*访问顶点k的未曾访问的顶点*/ visitedp-adjvex=1; EnQueue( 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 最小生成树641 生成树及最小生成树1生成树一个连通图的生成树是是一个极小连通子图，它含有图中全部顶

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

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

23、，则T=( U，TE) 便是G的一棵最小生成树。 普利姆算法逐步增加集合U中的顶点，直至U=V为止。 10 108 612 71012 61015 5图 6.14普 里 姆 算 法 构 造 最 小 生 成 树 的 过 程v3v4v0v1 v2v5 v0 v4v0(a) (b) (c)(d) (e)(f) (g) 5 v3v4v0 10 5 v3v4v0 v210 5 v3v4v0 v 2v5 7 10 5 v3v4v0v1 v2v5 710 66 6 2算法的实现 为了实现普里姆算法，需要附设一个辅助数组closedge，以记录从U到VU的具有最小权值的边。其数据类型定义如下：struct c

24、losedge VexType adjvex ; int lowcost;closedgeMaxSize; 对于每个顶点vi VU，在辅助数组closedge 中存在一个分量closedgei，其中closedgei.lowcost存储所有与v i邻接的、从U到VU的那组边中的最小边上的权值，显然有closedgei.lowcostMincost(u ,vi)|u U，其中cost (u ,vi)表示边(u ,vi)的权值。一旦顶点vi并入U，则closedgei.lowcost置为零；而closedgei.adjvex存储依附于该边的U中的顶点。 图6.15展示了在图6.14所示的构造最小生

25、成树的过程中，辅助数组closedge中各分量值的变化情况。P161 算法描述如下：int LocatVex(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) clos

26、edgej.adjvex=u0; closedgej.lowcost=g.arcskj; closedgek.lowcost=0; /*初始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+) /*重新调整clos

27、edge*/ if (g.arcskjclosedgej.lowcost) closedgej.lowcost=g.arcskj; closedgej.adjvex=g.vexsk; /*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中求

28、出权值最小的边的顶点序号min,且vmin V-U*/ for(i=0;ivexnum;i+) if(closedgei.lowcost!=0) break; min=i; for(i=0;ivexnum;i+) if (closedgei.lowcost!=0 return (min); /*Mininum*/假设网中有n个顶点，普里姆算法中有两个循环，所以时间复杂度为（n），它与网中边的数目无关，因此普里姆算法适合于求边稠密的网的最小生成树。 643 克鲁斯卡尔算法 基本思想 : 按权值递增的次序来选择合适的边构成最小生成树 。假设G（V，E）是连通网，最小生成树T（V，TE）。初始时，T

29、E，即T仅包含网G的全部顶点，没有一条边，T中每个顶点自成一个连通分量。算法执行如下操作：在图G的边集E中按权值递增次序依次选择边（u,v），若该边依附的顶点u,v分别是当前的两个连通分量中的顶点，则将该边加入到TE中；若u,v是当前同一个连通分量中的顶点，则舍去此边而选择下一条权值最小的边。依此类推直到T中所有顶点都在同一连通分量上为止，此时T便是G的一棵最小生成树。 与普里姆算法不同，克鲁斯卡尔算法是逐步增加生成树的边。 克鲁斯卡尔算法可描述如下：T=(V,);While (T中的边数en-1) 从E中选取当前权值最小的边（u,v）；if(u,v)并入T之后不产生回路)将边（u,v）并入T

30、中；else 从E中删去边（u,v）； 可以证明克鲁斯卡尔算法的时间复杂度是（eloge），其中e是网G的边的数目。克鲁斯卡尔算法适合于求边稀疏的网的最小生成树。 现以图6.14(a)所示的网为例，按克鲁斯卡尔算法构造最小生成树。其构造过程如图6.16所示。 5 56 7 5610 7 5 6 1010 6图 6.16 kruskal算 法 构 造 最 小 生 成 树 的 过 程v3v4v0v1 v2v5(a) v3v4v0v1 v2v5 v3v4v0v1 v2v5v3v4v0v1 v2v5 v3v4v0v1 v2v5(d) (c)(b) (e) 7 5 65 最短路径 问题提出用带权的有向图

31、表示一个地区的交通运输网，图中：顶点表示城市边上的权 表示城市间的公路权表示两个城市间的距离，或者表示通过这段公路所需的时间或需要花费的代价等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中， 各边上权值之和最小的一条路径最短路径从某个源点到其余各顶点的最短路径 136 717285 3230v1 v5v0v2 v4v6 9(a)有 向 网 络v3 最 短 路 径 长 度 8 13 19 21 13 20(b)从 源 点 v0到 其 余 各 顶 点 的最 短 路 径 和 长 度图 6.17有 向 网 络 及 从 源 点 到 其 余 各 顶 点 的 最 短 路 径 和 长 度 迪杰斯特拉(

32、Dijkstra)算法按路径长度递增的次序产生最短路径的算法 基本思想 ：把V分成两组：S：已求出最短路径的顶点的集合,V-S=T：尚未确定最短路径的顶点集合初始时，S中只包含源点v0，T中包含除源点外的其余顶点，此时各顶点的当前最短路径长度为源点到该顶点的弧上的权值，然后按最短路径长度递增的次序逐个把T中的顶点加到S中去，直至从v0出发可以到达的所有顶点都包括到S中为止。保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长

33、度 设有向图G有n个顶点（v0为源点），其存储结构用邻接矩阵表示。算法实现时需要设置三个数组sn、distn和pathn。s用以标记那些已经找到最短路径的顶点集合S，若si=1,则表示已经找到源点到顶点vi的最短路径，若si=0，则表示从源点到顶点vi的最短路径尚未求得，数组的初态为：s0=1，si=0,i=1,2,n-1，表示集合S中只包含一个顶点v0。数组dist记录源点到其他各顶点的当前的最短距离，其初值为： disti=g.arcs0i i=1,2,n-1 path是最短路径的路径数组，其中pathi表示从源点v 0到顶点vi之间的最短路径上该顶点的前驱顶点，若从源点到顶点vi无路径，

34、则pathi=-1。 求最短路径步骤初使时令 S=V0,T=其余顶点，T中顶点对应的距离值若存在，为弧上的权值若不存在，为从T中选取一个其距离值为最小的顶点W，加入S，即令sw=1；对T中顶点的距离值进行修改：若加进W作中间顶点，从V 0到Vi的距离值比不加W的路径要短，则修改此距离值，即从原来的distj和distw+g.arcswj中选择较小的值作为新的distj。 重复上述步骤，直到S中包含所有顶点，即S=V为止 网采用邻接矩阵做存储结构，用迪杰斯特拉算法求最短路径的算法描述如下：void Dijkstra(AdjMatrix g, int v0, int path, int dist)

35、 /*求有向网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 /* MAXINT 为int类型的最大值*/ else pathv=-1； distv0=0; sv0=1; *初始时源点v0 S集* *循环求v0到某个顶点v的最短路径，并将v加入S集*for (i=0;i g.vexnum-1;i+) min=MAXINT; /*MAXI

36、NT是一个足够大的数*/ v=-1; /*v记录找到的最小距离的顶点序号*/ for (w=0;wg.vexnum;w+) if(!sw min=distw; if (v!=-1)/*找到最小距离的顶点v*/ sv=1; *顶点v并入S* for (j=0;jg.vexnum;j+) *更新当前最短路径及距离* if(!sj pathj=v; /*if */ /*if*/ /*for */*Dijkstra */ 通过pathi向前推导直到v0为止，可以找出从v0到顶点vi的最短路径。例如，对于图6.17(a)的有向网络，按上述算法计算出的path数组的值为： 求顶点v0到顶点v3的最短路径的

37、计算过程为：path3=2,说明路径上顶点v 3之前的顶点是顶点v2；path2=1, 说明路径上顶点v2之前的顶点是顶点v1；path1=0,说明路径上顶点v1之前的顶点是顶点v0。则顶点v0到顶点v3的路径为v0，v1，v2，v3。 迪杰斯特拉算法中有两个循环次数为顶点个数n的嵌套循环，所以其时间复杂度为（n2）。0-1 10 21 32 43 50 65 输出最短路径的算法描述如下：void PrintPath(int v0, int p, int d, int vexnum)*输出源点v0到其余顶点的最短路径和路径长度,路径逆序输出* for (i=0;ivexnum;i+) if(d

38、iMAXINT 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”,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

39、- v3 -v2 -v1- v0:21v5-v0 ：13v6- v5- v0:20 给出一个含有n个顶点的带权有向图，求其每一对顶点之间的最短路径。解决这个问题的一种方法是：每次以一个顶点为源点，执行迪杰斯特拉算法，求得从该顶点到其他各顶点的最短路径；重复执行n次之后，就能求得从每一个顶点出发到其他各顶点的最短路径。 66 拓扑排序问题提出：学生选修课程问题 顶点表示课程 有向弧表示先决条件，若课程i是课程j的先决条件，则图中有弧 学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序定义 AOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity

40、 On Vertex network)，简称AOV网 若是网中的一条弧，则称顶点i优先于顶点j，i是j的直接前驱，或称j是i的直接后继。 一个顶点如果没有前驱，则该顶点所表示的子工程可独立于整个工程，即该子工程的开工不受其他子工程的约束。否则，一个子工程的开工必须以其前驱所代表的子工程的完工为前提条件。 AOV网中不允许有回路，这意味着某项活动以自己为先决条件 拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫 检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环 对AOV网进行拓扑排序的方

41、法和步骤是： (1)在有向图中选一个没有前驱（即入度为0）的顶点并且输出之。 (2)从图中删去该顶点和所有以该顶点为弧尾的弧。 重复上述两步，直至全部顶点均被输出，或者当前网中不再存在没有前驱的顶点为止。操作结果的前一种情况 说明网中不存在有向回路，拓扑排序成功；后一种情况说明网中存在有向回路。 图6.20给出了一个按上述步骤求AOV网的拓扑序列的例子。这样得到的一个拓扑排序序列为：v0，v4，v1，v 2，v5，v3。 v4 v1v0 图 6.20 AOV网 及 其 拓 扑 有 序 序 列 的 产 生 过 程v2 v3v5(a) AOV网 (b) 输 出 v0后v3v5(e) 输 出 v2后

42、后 v3(f) 输 出 v5后后(c) 输 出 v4后后 v2 v3v5(d) 输 出 v1后后 v4 v1 v2 v3v5v1 v2 v3v5 拓扑排序算法的实现 用邻接表作为有向图的存储结构，并且在表头结点中增设一个入度域（indegree），存放顶点的入度。每个顶点的入度域的值随邻接表动态生成过程累计得到。例如图6.21所示为图6.20(a)的AOV网的邻接表。入度为0的顶点即为没有前驱的顶点，删除顶点及以它为弧尾的弧的操作，则可转换为将它的所有弧头顶点的入度域减来实现。为了避免重复检测入度为零的顶点，可另设一个栈来暂时存放所有入度为零的顶点。 拓扑排序算法可形式地描述如下：(1)扫描顶

43、点表，将入度为零的顶点入栈；(2)while (栈非空) 将栈顶顶点vj弹出并输出之； 在邻接表中查vj的直接后继vk，把vk的入度减，若vk的入度为零则进栈；(3)若输出的顶点数小于n,则表示有回路；否则拓扑排序正常结 束。 算法中的邻接表的结构描述如下。#define MaxSize 顶点数目typedef struct ArcNode int adjvex; /*邻接点序号*/ struct ArcNode *nextarc; otherinfo info;ArcNode; /*边结点*/typedef struct VertexNode VertexType data; int ind

44、egree; /*入度*/ 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=-1; n=0;for(j=0;jvexnum;j+) /*入度为0的顶点进栈*/ if(g-vertexj.indegree=0) s+top

45、=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*/ /*while*/ printf(nn=%dn,n);if(nvexnum) printf(The

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

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

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

49、g,int u,int v) /*找一条从u到v的简单路径*/ 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);

50、/*输出路径*/ else if (!visitedq-adjvex) pathu=q-adjvex; DFSPath(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 */ 68 实训例题实训例题1 设计学习计划 【问题描述】软件专业的学生要学习一系列课程，其中有些课程在其先修课程完成后才能学习，如6.6节图6.19所示。假设每门课程的学习时间为一学期，试

51、为该专业的学生设计学习计划，使他们能够在最短的时间内修完这些课程。【基本要求】功能：为学生设计学习计划。输入：输入学生需要学习的课程之间的先修关系。即把课程之间的先修关系表示为AOV网，输入该网。输出：学生学习课程的计划，即输入的AOV网的拓扑序列。 【数据结构】采用AOV网表示课程之间的先修关系，因为在算法中要涉及求顶点的邻接点，所以存储结构采用邻接表比较合适。其类型描述为：typedef int VertexType; /*为简单起见，顶点信息设为顶点序号*/typedef struct ArcNode int adjvex; /*邻接点序号*/ struct ArcNode *nexta

52、rc; otherinfo info;ArcNode; /*边结点*/typedef struct VertexNode VertexType data; int indegree; /*入度*/ ArcNode *firstarc;VertexNode; /*表头结点*/typedef struct VertexNode vertexMaxSize; int vexnum,arcnum;AdjList; /*图的邻接表*/ 【算法思想】 以顶点表示课程，弧表示课程之间的先修关系，对任意两门课程i和j，如果i是j的先修课，则在顶点i和顶点j之间画一条弧，按题中条件建立有向图。依题意，该问题的求

53、解便成了求有向图的拓扑有序序列。在算法中，在邻接表的表头结点中加入了存放顶点入度的域indegree，每个顶点的入度域初始值均为0，随着弧的输入动态地累计得到各顶点的入度。 在拓扑排序的过程中，和6.6节中介绍的方法不同，没有为堆栈专门开辟空间，而是利用表头结点数组中入度为0的顶点的indegree域进行链接形成链栈。 【模块划分】整个算法分三个模块 建立有向图的邻接表CreateAdjList; 以邻接表作存储结构实现拓扑排序TopSort； 主函数main()，功能是建立邻接表的表头数组，调用CreateAdjList函数形成有向图的邻接表，调用TopSort函数求得学习计划。 【源程序】

54、#include #define MaxSize 50typedef int VertexType; /*为简单起见，顶点信息设为顶点序号*/typedef struct ArcNode int adjvex; /*邻接点序号*/ struct ArcNode *nextarc;ArcNode; /*边结点*/typedef struct VertexNode VertexType data; int indegree; /*入度*/ ArcNode *firstarc;VertexNode; /*表头结点*/typedef struct VertexNode vertexMaxSize; i

55、nt vexnum,arcnum; AdjList; /*图的邻接表*/ void CreateAdjList(AdjList *g) /*建立图的邻接表*/ int n,e,i,j,k; ArcNode *p;printf(“input vexnum,arcnum:”); scanf(“%d%d”, g-vexnum=n; g-arcnum=e; for (i=0;ivertexi.data=i;g-vertexi.indegree=0;g-vertexi.firstarc=NULL;for (k=0;kadjvex=j; p-nextarc=g-vertexi.firstarc;/*新生成

56、结点插入对应单链(边)表头部*/ g-vertexi.firstarc=p; g-vertexj.indegree+; /*弧的终端顶点入度加1*/ void TopSort(AdjList g) /*由拓扑排序算法求学习计划* ArcNode *p; int m,i,j,k,top; top=-1; /*栈初始化*/ for (i=0;iadjvex;g.vertexk.indegree-; /*以已输出顶点为弧尾的弧的终端顶点入度减1*/ if (g.vertexk.indegree=0)/*减1后入度为0，则进栈*/ g.vertexk.indegree=top; top=k; p=p-

57、nextarc; if (mg.vexnum) /*拓扑排序过程中输出的顶点数小于有向图的顶点数*/printf(“there is a cycle in the gragh!n”);/* TopSort */ main() AdjList g;CreateAdjList( /*建立有向图的邻接表*/ TopSort(g); /*进行拓扑排序*/ 实训例题2 渡河问题 【问题描述】有一农夫带着一匹狼、一只羊和一筐白菜，想从河的左岸乘船到右岸。但由于船太小，农夫每次只能带一样东西过河，而且，如果没有农夫看管，狼会吃掉羊，羊会吃掉白菜。设计一个方案，使农夫能把每样东西都安全地送过河。【基本要求】功

58、能：设计过河方案。输入：输入表示安全状态转换的图。输出：过河方案。【算法思想】从表面上看，这个问题并不是一个图的问题，但可以把它用图表示出来，从而转换为一个图的问题。在这个问题的解决过程中，农夫需要多次乘船往返于两岸之间，每次可以带一样东西或者自己单独过河，每一次过河都会使农夫、狼、羊和白菜所处的位置发生变化。如果用一个四元组（Farmer，Wolf，Sheep，Vegetable）表示当前农夫、狼、羊和白菜所处的位置，其中每个元素可以是0或1，0表示在左岸，1表 示在右岸。这样，对这四个元素的不同取值可以构成16种不同的状态，初始时的状态则为（0，0，0，0），最终要达到的目标为（1，1，1

59、，1）。状态之间的转换可以有下面四种情况： (1) 农夫不带任何东西过河，可表示为：（Farme，Wolf，Sheep，Vegetable）(!Farme，Wolf，Sheep，Vegetable)(2) 当农夫和狼在相同位置时，表示农夫带狼过河，即当Farmer=Wolf时：（Farme，Wolf，Sheep，Vegetable）(!Farme，!Wolf，Sheep，Vegetable)(3) 当农夫和羊在相同位置时，表示农夫带羊过河，即当Farmer=Sheep时：（Farme，Wolf，Sheep，Vegetable）(!Farme，Wolf，!Sheep，Vegetable)(4)

60、当农夫和白菜在相同位置时，表示农夫带白菜过河，即当Farmer= Vegetable时：（Farme，Wolf，Sheep，Vegetable）(!Farme，Wolf，Sheep，!Vegetable)其中：运算!代表非运算，即对于任何元素x，有：1，当x0时!x0当x1时（0，0，0，0）（1，0，1，0）（1，1，1，0）（1，0，1，1）（0，0，1，0）（0，0，0，1）（0，1，0，0）（1，1，0，1）（0，1，0，1）（1，1，1，1）在这16种状态中，有些状态是不安全的，是不允许出现的，如（1，0，0，1）表 示农夫和白菜在右岸，而狼和羊在左岸，这样狼会吃掉羊。如果从16种状

61、态中删去这些不安全状态，将剩余的安全状态之间根据上面的转换关系连接起来，就得到如图6.24所示的图。图6.24渡河问题的状态图这样，原始问题就转换为在图6.24中寻找一条从顶点（0，0，0，0）到顶点（1，1，1，1）的路径问题。 【数据结构】采用邻接矩阵和邻接表都可以完成求图中两顶点间的路径问题，这里，采用邻接矩阵存储结构。其中图中的每个顶点结点包括四个域，类型描述为：# define MaxSize 20 /*最大顶点个数*/*定义图的顶点类型*/typedef struct int Farmer, Wolf, Sheep, Vegetable;VexType;/*图的邻接矩阵存储结构定义

62、为：*/ typedef struct VexType vexsMaxSize; /*顶点数组*/ int arcsMaxSize MaxSize; /*邻接矩阵*/ int vexnum, arcnum; /*图的当前顶点数和边数*/ AdjMatrix; 【模块划分】在这个问题中，首先需要自动生成图的邻接矩阵，具体方法是先生成各种安全状态结点，存放在顶点数组中；再根据状态之间的转换关系形成顶点之间的所有边，保存在邻接矩阵中。在建立了图的邻接矩阵存储结构后，利用深度优先搜索思想求出从顶点(0，0，0，0)至顶点（1，1，1，1）的一条简单路径。一共分7个模块：Locate（）函数：查找顶点的

63、序号；IsSafe（）函数：判断顶点所表示的状态是否安全；IsConnected( )函数：判断两个状态之间是否可以转换；GreateGraph( )函数：建立图的邻接矩阵；PrintPath( )函数：输出路径；DFSPath( )函数：求两个顶 点之间的路径；main( )函数：调用各函数完成功能。 【源程序】# define MaxSize 20 /*最大顶点个数*/*定义图的顶点类型*/typedef struct int Farmer, Wolf, Sheep, Vegetable;VexType;/*图的邻接矩阵存储结构定义为：*/ typedef struct VexType v

64、exsMaxSize; /*顶点数组*/ int arcsMaxSizeMaxSize; /*邻接矩阵*/ intvexnum, arcnum; /*图的当前顶点数和边数*/ AdjMatrix; int visitedMaxSize; int path MaxSize;int Locate(AdjMatrix *g, int F, int W, int S, int V)/*查找顶点（F，W，S，V）在顶点数组中的位置*/ int i; for (i=0;ivexnum; i+) if (g-vexsi.Farmer=Freturn(-1);/* Locate */ int IsSafe(i

65、nt F, int W, int S, int V) /*判断状态（F，W，S，V）是否安全*/ if (F!=S else return(1); /*IsSafe*/int IsConnected(AdjMatrix *g, int i, int j)/*检查第i个和第j个状态之间是否可转换*/ int k; k=0; if (g-vexsi.Wolf!=g-vexsj.Wolf) k+; if (g-vexsi.Sheep!=g-vexsj.Sheep) k+; if (g-vexsi.Vegetable!=g-vexsj.Vegetable) k+; if (g-vexsi.Farmer

66、!=g-vexsj.Farmer else return(0);/* IsConnected */ void CreateGraph(AdjMatrix *g) int i, j, F, W, S, V; i=0; for (F=0; F=1; F+) /*形成所有安全的状态结点*/ for (W=0; W=1; W+) for (S=0; S=1; S+) for (V=0; Vvexsi.Farmer=F; g-vexsi.Wolf=W; g-vexsi.Sheep=S; g-vexsi.Vegetable=V; i+; g-vexnum=i;for (i=0; ivexnum; i+) for (j=0; jvexnum; j+) if ( IsConnected(g, i, j) g-arcsij=g-arcsji=1; else g-arcsij=g-arcsji=0;return;/* CreateGraph */ void PrintPath(AdjMatrix *g, int u, int v) /*输出从u到v的简单路径*/ int k;k=u; while ( k!