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

第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为无向图。通常用(vi，vj)表示顶点vi和vj间的无向边。 有向图若图G中表示边的顶点对是有序的（称有向边），则称图G为有向图。通常用表示从顶点vi到顶点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=，。,6.1.2 图的基本术语,邻接点在无向图G(V，E)中，若边(vi，vj)E，则称顶点vi和vj互为邻接点（Adjacent），或vi和vj相邻接，并称边(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)条边，即图中每对顶点之间都有一条边，则称该无向图为无向完全图。若有向图中有n( n 1)条弧，即图中每对顶点之间都有方向相反的两条弧，则称该有向图为有向完全图。有很少条边或弧（enlogn）的图称为稀疏图，反之称为稠密图。,子图：假设有两个图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。路径上边或弧的数目称为路径长度。如果路径的起点和终点相同（即vv），则称此路径为回路或环（Cycle）。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。,连通图、连通分量：在无向图G中，若从顶点vi到顶点vj(ij)有路径相通，则称vi和vj是连通的。如果图中任意两个顶点vi和vj(ij)都是连通的，则称该图是连通图（Connected Graph）。无向图中极大连通子图称为连通分量（Connected Component ）。强连通图、强连通分量：在有向图中，若任意两个顶点vi和vj都连通，即从vi到vj和从vj到vi 都有路径相通，则称该有向图为强连通图，例如图6.2 中G4就是强连通图。有向图中的极大强连通子图称为该有向图的强连通分量。,权、网：图的每条边或弧上常常附上一个具有一定意义的数值，这种与边或弧相关的数值称为该边（弧）的权（Weight）。边或弧上带权的连通图称为网（Network）。如图6.6所示。,62 图的存储结构 621 邻接矩阵,1邻接矩阵 这种存储结构采用两个数组来表示图：一个是一维数组，存储图中的所有顶点的信息；另一个是二维数组即邻接矩阵，存储顶点之间的关系。 设G=（V，E）是具有n个顶点的图，顶点序号依次为0，1，n-1，即V(G)=v0，v1，vn-1，则图G的邻接矩阵是具有如下性质的n阶方阵：,若G是网，则其邻接矩阵是具有如下性质的n阶方阵： Wij 若（vi，vj）或E Aij= 反之 这里，Wij表示边(vi ，vj)或弧上的权值；代表一个计算机内允许的、大于所有边（弧）上权值的正整数。 例如图6.6所示网G6的邻接矩阵如图6.8所示, 30 60 20,30 10 90, 10 50 ,60 50 70,20 90 70 ,A=,类型描述 : #define MaxSize 顶点数目 typedef struct VexType vexsMaxSize; /*顶点数组*/ int arcsMaxSize MaxSize; /*邻接矩阵*/ int vexnum,arcnum; /*顶点数，边（弧）数*/ AdjMatrix;,特点 : 无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。 对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度TD（vi）；对于有向图，邻接矩阵的第i行非零元素的个数正好是第i个顶点的出度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 VexType void CreatAMgraph(AdjMatrix *g) /*建立无向图的邻接矩阵g*/ printf(“please input vexnum and arcnum:n”); scanf(“%d”, /*CreatAMgraph*/,其执行时间是O（n+n2+e），其中O（n2 ）的时间耗费在邻接矩阵的初始化操作上。因为en2，所以，算法CreatMgraph的时间复杂度是O（n2）。,6.2.2 邻接表,1邻接表 在邻接表中，对图中的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的一条边（对有向图是以顶点vi为弧尾的弧），称为边结点，由三个域组成，其结构如下： 其中邻接点域（adjvex）存放依附于该边的另一个顶点在图中的序号，链域（nextarc）指向依附于顶点vi的下一条边的边结点，info存储与边或弧相关的信息，如权值等，当图中的边（或弧）不含有信息时，可以没有该域。一般称该单链表为边表。 对每个边表附设一个表头结点，所有的边表的表头结点存放在一个一维数组中，共同构成一个表头结点表。表头结点由两个域组成，其结构为： 其中data域存放顶点的信息，firstarc域为指针域，它存放与该顶点相邻接的所有顶点组成的单链表即边表的头指针。,例如图6.1中的G1和G2的邻接表如图6.9所示:,类型描述 #define MaxSize 顶点数目 typedef struct ArcNode int adjvex; struct ArcNode *nextarc; otherinfo info; ArcNode; /*边结点*/ typedef struct VertexNode VertexType data; ArcNode *firstarc; VertexNode; /*表头结点*/ typedef struct VertexNode vertexMaxSize; int vexnum, arcnum; AdjList; /*图的邻接表*/,特点 在无向图的邻接表中，第i个链表中边结点的个数为顶点vi的度。 在有向图的邻接表中，第i个链表中的边结点的个数只是顶点vi的出度。其入度为邻接表中所有adjvex域的值为i的边结点的数目。 在有向图的邻接表中，若要求vi的入度，必须扫描整个邻接表，统计邻接点域（adjvex）的值为i的边结点的数目。显然，这是很费时间的。为了便于确定有向图中顶点的入度，可以另外再建立一个逆邻接表，使第i个链表表示以vi为弧头的所有的弧。图6.10即为图6.1中G2的逆邻接表。,2建立图的邻接表 首先将邻接表的表头结点数组初始化，第i个顶点的data 域初始化为从键盘输入的字符，firstarc域初始化为NULL。然后读入顶点对（i，j）（i，j为顶点的序号），产生两个边结点，将j放入到第一个边结点的adjvex域，将该结点链到邻接表的表头结点数组的第i个表头结点的firstarc域上；将i放入到第二个边结点的adjvex域，将该结点链到邻接表的表头结点数组的第j个表头结点的firstarc域上。重复这个过程，直到所有的边输入完为止。,算法描述 : typedef char VertexType; void CreateALGraph(AdjList *g) /*建立无向图的邻接表*/ printf(“please input vexnum and arcnumn”); scanf(“dd“， scanf(“%c”,&g-vertexi.data)； /*读入顶点信息*/ g-vertexi.firstarc=NULL；/*边表置为空表*/ ,for(k=0；karcnum；k+)/*建立边表*/ printf(“please input edges:n”); scanf(“dd“， /*邻接点序号为i*/ s-nextarc=g-vertexj.firstarc； /*将新结点*s插入顶点vj的边表头部*/ g-vertexj.firstarc=s； /* CreateALGraph */,在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表的时间复杂度为O(n+e)，否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为O(n*e)。 注意：从逻辑上说，一个顶点的所有邻接点之间并没有先后之分，但当图的具体的存储结构建立后，一个顶点的所有邻接点之间就可以分出先后。,6.2.3邻接矩阵和邻接表的比较,（1）邻接矩阵是一种静态的存储结构；邻接表是一种动态的存储结构。 （2）邻接矩阵是顺序存储结构，因此相应的算法实现较简单；邻接表中有指针，因此相应的算法较为复杂。 （3）邻接矩阵占用的存储单元数目只与图中顶点个数有关，而与边（弧）的数目无关，对于一个具有n个顶点e条边的图G，其邻接矩阵所占存储单元为n2，而其邻接表（和逆邻接表）中有n个表头结点和2e个边（弧）结点；在稀疏图中边的数目远远小于n2（即en2），这时用邻接表比用邻接矩阵节省存储空间；若是稠密图，因邻接表中要附加链域，则选取邻接矩阵更合适。 （4）在邻接矩阵中，很容易判定任意两个顶点vi，vj之间是否有边或弧相连，只要判定矩阵中的第i行第j列上的元素的值即可；但是在邻接表中，需搜索第i个或第j个边表，最坏情况下要耗费O（n）时间。 (5）在邻接矩阵中求边的数目e，必须检测整个矩阵，所耗费的时间是O（n2），与e的大小无关；而在邻接表中，只要对每个边表的结点个数计数即可求得e，所耗费的时间是O（e+n）。因此，当en2时，采用邻接表更节省时间。,6.3 图的遍历,图的遍历就是从图中任意给定的的顶点（称为起始顶点）出发，按照某种搜索方法，访问图中其余的顶点，且使每个顶点仅被访问一次的过程。 图的遍历是一种基本操作 。 图的任一顶点都可能和其余顶点相邻接，因此在遍历图的过程中，在访问了某个顶点后，可能沿着某条路径搜索后又回到该顶点，为避免某个顶点被访问多次，在遍历图的过程中，要记下每个已被访问过的顶点。为此，可增设一个访问标志数组visitedn，用以标识图中每个顶点是否被访问过。每个visitedi的初值置为零，表示该顶点未被访问过。一旦顶点vi被访问过，就将visitedi置为1，表示该顶点已被访问过。 两种遍历图的算法：深度优先搜索遍历算法和广度优先搜索遍历算法,6.3.1 连通图的深度优先搜索,基本思想 : 假定以图中某个顶点vi为起始顶点，首先访问起始顶点，然后选择一个与顶点vi相邻且未被访问过的顶点vj为新的起始顶点继续进行深度优先搜索，直至图中与顶点vi邻接的所有顶点都被访问过为止。,图6.11（a）中的图G为例说明深度优先搜索过程。 遍历过程见图6.11 (b)，得到的顶点的访问序列为v0v1v3v4v2v5v7v6。 注意：用深度优先搜索法遍历一个没有给定具体存储结构的图得到的访问序列不唯一。但就一个具体的存储结构所表示的图而言，其遍历序列应该是确定的。,以邻接矩阵作为图的存储结构的深度优先搜索遍历算法描述如下： int visited MaxSize=0; void DFS1(AdjMatrix *g, int i) /*从第i个顶点出发深度优先遍历图G，G以邻接矩阵表示*/ printf(“%3c”,g-vexsi); /*访问顶点vi*/ visitedi=1; for (j=0;jvexnum;j+) if (g-arcsij=1) /*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算法得知，遍历图的过程实质上是对每个顶点搜索其邻接点的过程。耗费的时间取决于所采用的存储结构。假设图中有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(a)中图G为例说明广度优先搜索的过程 顶点访问序列为： v0v1v2v3v4v5v6v7。,以邻接矩阵作为图的存储结构的广度优先搜索遍历算法描述如下： int visitedMaxSize=0; void BFS1(AdjMatrix g,int i) /*从第i个顶点出发广度优先遍历图G，G以邻接矩阵表示*/ int k; Queue Q; /*定义一个队列*/ printf(“%3c”,g.vexsi); /*访问顶点vi */ visitedi=1; InitQueue( /* vi入队列 */,while (!Empty(Q) DeQueue( /* vj 入队列 */ /*BFS1 */,以邻接表作为图的存储结构的广度优先搜索遍历算法描述如下： int visitedMaxSize=0; void BFS2(AdjList g,int i) /*从第i个顶点出发广度优先遍历图G，G以邻接表表示*/ int k,; ArcNode *p; Queue Q; /*定义一个队列*/ printf(“%3c”,G.vertexi.data); /*访问顶点vi */ visitedi=1; InitQueue( /* vi 入队列 */,while (!Empty(Q) DeQueue( /*求k的下一个邻接点*/ /*BFS2 */,算法分析： 分析上述算法，每个顶点至多进一次队列，所以算法中的内、外循环次数均为n次，故算法 BFS1的时间复杂度为O（n2）；若采用邻接表存储结构，广度优先搜索遍历图的时间复杂度与深度优先搜索是相同的。,6.3.3 非连通图的遍历,如果给定的图是不连通的，则调用上述遍历算法（深度或广度优先搜索算法）只能访问到起始顶点所在的连通分量中的所有结点，其它连通分量中的结点是访问不到的。为此，需从每一个连通分量中选取起始顶点，分别进行遍历，才能访问到图中的所有顶点。 深度优先搜索遍历非连通图的算法描述如下： void DFSUnG(AdjMatrix *g) int i for (i=0;ivexnum;i+) if visitedi=0) DFS(g,i); ,6.4 最小生成树 641 生成树及最小生成树,1生成树 一个连通图的生成树是是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。 一个连通图的生成树是不惟一的。 由深度优先搜索得到的生成树称为深度优先生成树；由广度优先搜索得到的生成树称为广度优先生成树。,2最小生成树 在一个连通网的所有生成树中，各边的权值之和最小的那棵生成树称为该连通网的最小代价生成树（Minimum Cost Spanning Tree），简称为最小生成树。 构造最小生成树的算法很多，其中多数算法都利用了最小生成树的一种称之为MST的性质。 MST性质：假设 G=（V，E）是一连通网，U 是顶点集V的一个非空子集。 若（u ，v）是一条具有最小权值的边，其中uU，vV-U，则必存在一棵包含边（u ，v）的最小生成树。 常用的构造最小生成树的算法有普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。,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为止。此时TE中必有n-1条边，则T=( U，TE) 便是G的一棵最小生成树。 普利姆算法逐步增加集合U中的顶点，直至U=V为止。,2算法的实现 为了实现普里姆算法，需要附设一个辅助数组closedge，以记录从U到VU的具有最小权值的边。其数据类型定义如下： struct closedge VexType adjvex ; int lowcost; closedgeMaxSize; 对于每个顶点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 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) closedgej.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+) /*重新调整closedge*/ 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中求出权值最小的边的顶点序号min,且vminV-U*/ for(i=0;ivexnum;i+) if(closedgei.lowcost!=0) break; min=i; for(i=0;ivexnum;i+) if (closedgei.lowcost!=0 /*Mininum*/ 假设网中有n个顶点，普里姆算法中有两个循环，所以时间复杂度为（n），它与网中边的数目无关，因此普里姆算法适合于求边稠密的网的最小生成树。,643 克鲁斯卡尔算法,基本思想 : 按权值递增的次序来选择合适的边构成最小生成树 。假设G（V，E）是连通网，最小生成树T（V，TE）。初始时，TE，即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中； else 从E中删去边（u,v）； 可以证明克鲁斯卡尔算法的时间复杂度是（eloge），其中e是网G的边的数目。克鲁斯卡尔算法适合于求边稀疏的网的最小生成树。,现以图6.14(a)所示的网为例，按克鲁斯卡尔算法构造最小生成树。其构造过程如图6.16所示。,65 最短路径,问题提出 用带权的有向图表示一个地区的交通运输网，图中： 顶点表示城市 边上的权 表示城市间的公路 权表示两个城市间的距离，或者表示通过这段公路所需的时间或需要花费的代价等 问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中， 各边上权值之和最小的一条路径最短路径 从某个源点到其余各顶点的最短路径,迪杰斯特拉(Dijkstra)算法 按路径长度递增的次序产生最短路径的算法 基本思想 ： 把V分成两组：S：已求出最短路径的顶点的集合,V-S=T：尚未确定最短路径的顶点集合 初始时，S中只包含源点v0，T中包含除源点外的其余顶点，此时各顶点的当前最短路径长度为源点到该顶点的弧上的权值，然后按最短路径长度递增的次序逐个把T中的顶点加到S中去，直至从v0出发可以到达的所有顶点都包括到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中只包含一个顶点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中选择较小的值作为新的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 *初始时源点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 /*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的嵌套循环，所以其时间复杂度为（n2）。,输出最短路径的算法描述如下： void PrintPath(int v0, int p, int d, int vexnum) *输出源点v0到其余顶点的最短路径和路径长度,路径逆序输出* for (i=0;ivexnum;i+) if(diMAXINT /* PrintPath */,对于图6.17(a)的有向网络，其邻接矩阵如图6.18(a)所示，利用Dijkstra算法计算从顶点v0到其他各顶点的最短路径的动态执行情况如图6.18(b）所示。P166,最后的输出结果是： v- v0:8 v2- v1- v0:13 v3 -v2 -v1- v0:19 v4- v3 -v2 -v1- v0:21 v5-v0 ：13 v6- v5- v0:20,给出一个含有n个顶点的带权有向图，求其每一对顶点之间的最短路径。解决这个问题的一种方法是：每次以一个顶点为源点，执行迪杰斯特拉算法，求得从该顶点到其他各顶点的最短路径；重复执行n次之后，就能求得从每一个顶点出发到其他各顶点的最短路径。,66 拓扑排序,问题提出：学生选修课程问题 顶点表示课程 有向弧表示先决条件，若课程i是课程j的先决条件，则图中有弧 学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序 定义 AOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网 若是网中的一条弧，则称顶点i优先于顶点j，i是j的直接前驱，或称j是i的直接后继。 一个顶点如果没有前驱，则该顶点所表示的子工程可独立于整个工程，即该子工程的开工不受其他子工程的约束。否则，一个子工程的开工必须以其前驱所代表的子工程的完工为前提条件。 AOV网中不允许有回路，这意味着某项活动以自己为先决条件,拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫 检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环 对AOV网进行拓扑排序的方法和步骤是： (1)在有向图中选一个没有前驱（即入度为0）的顶点并且输出之。 (2)从图中删去该顶点和所有以该顶点为弧尾的弧。 重复上述两步，直至全部顶点均被输出，或者当前网中不再存在没有前驱的顶点为止。操作结果的前一种情况说明网中不存在有向回路，拓扑排序成功；后一种情况说明网中存在有向回路。,图6.20给出了一个按上述步骤求AOV网的拓扑序列的例子。 这样得到的一个拓扑排序序列为：v0，v4，v1，v2，v5，v3。,拓扑排序算法的实现 用邻接表作为有向图的存储结构，并且在表头结点中增设一个入度域（indegree），存放顶点的入度。每个顶点的入度域的值随邻接表动态生成过程累计得到。例如图6.21所示为图6.20(a)的AOV网的邻接表。入度为0的顶点即为没有前驱的顶点，删除顶点及以它为弧尾的弧的操作，则可转换为将它的所有弧头顶点的入度域减来实现。 为了避免重复检测入度为零的顶点，可另设一个栈来暂时存放所有入度为零的顶点。 拓扑排序算法可形式地描述如下： (1)扫描顶点表，将入度为零的顶点入栈； (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 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=-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*/ /*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 一个图的邻接表表示:,（1）该无向图如图6.23(a)所示。 （2）根据该无向图的邻接表表示，从顶点v0开始的深度优先遍历的序列为：v0v2v3v1v4v6v5，其相应的生成树如图6.23(b)所示；从顶点v0开始的广度优先遍历的序列为：v0v2v5v6v1v3v4，其相应的生成树如图6.23(c)所示。,【例2】以邻接表为存储结构，利用DFS搜索策略设计一个算法，求图中从顶点u到顶点v的一条简单路径，并输出该路径。 从顶点u开始，进行深度优先搜索，如果能够搜索到顶点v，则表明从顶点u到顶点v有一条路径。由于在搜索过程中每个顶点只访问一次，所以这条路径一定是简单路径。因此，只要在搜索过程中把当前的搜索线路记录下来，并在搜索到顶点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的简单路径*/ 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; 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所示。假设每门课程的学习时间为一学期，试为该专业的学生设计学习计划，使他们能够在最短的时间内修完这些课程。 【基本要求】 功能：为学生设计学习计划。 输入：输入学生需要学习的课程之间的先修关系。即把课程之间的先修关系表示为AOV网，输入该网。 输出：学生学习课程的计划，即输入的AOV网的拓扑序列。,【数据结构】 采用AOV网表示课程之间的先修关系，因为在算法中要涉及求顶点的邻接点，所以存储结构采用邻接表比较合适。其类型描述为： typedef int VertexType; /*为简单起见，顶点信息设为顶点序号*/ typedef struct ArcNode int adjvex; /*邻接点序号*/ struct ArcNode *nextarc; 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之间画一条弧，按题中条件建立有向图。依题意，该问题的求解便成了求有向图的拓扑有序序列。在算法中，在邻接表的表头结点中加入了存放顶点入度的域indegree，每个顶点的入度域初始值均为0，随着弧的输入动态地累计得到各顶点的入度。 在拓扑排序的过程中，和6.6节中介绍的方法不同，没有为堆栈专门开辟空间，而是利用表头结点数组中入度为0的顶点的indegree域进行链接形成链栈。,【模块划分】 整个算法分三个模块 建立有向图的邻接表CreateAdjList; 以邻接表作存储结构实现拓扑排序TopSort； 主函数main()，功能是建立邻接表的表头数组，调用CreateAdjList函数形成有向图的邻接表，调用TopSort函数求得学习计划。,【源程序】 #include #define MaxSize 50 typedef 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; int vexnum,arcnum; AdjList; /*图的邻接表*/,void CreateAdjList(AdjList *g) /*建立图的邻接表*/ int n,e,i,j,k; ArcNode *p; printf(“input vexnum,arcnum:”); scanf(“%d%d”, /*弧的终端顶点入度加1*/ ,void TopSort(AdjList g) /*由拓扑排序算法求学习计划* ArcNode *p; int m,i,j,k,top; top=-1; /*栈初始化*/ for (i=0;ig.vexnum;i+) if (g.vertexi.indegree=0) /*入度为0的顶点链入链栈，top指向栈顶*/ g.vertexi.indegree=top; top=i; m=0; printf(“topsort is :n”);,while (top!=-1) /*栈不空，进行拓扑排序 */ j=top; /*取栈顶元素*/ top=g.vertextop.indegree; /*删除栈顶元素*/ printf(“%4d”,g.vertexj.data); /*输出一个拓扑排序结点*/ m+; /*拓扑排序结点个数加1*/ p=g.vertexj.firstarc; while (p!=NULL) k= p-adjvex; g.vertexk.indegree-; /*以已输出顶点为弧尾的弧的终端顶点入度减1*/ if (g.vertexk.indegree=0)/*减1后入度为0，则进栈*/ g.vertexk.indegree=top