《图及有向图的应用》PPT课件.ppt

第4章图及有向图的应用,基本定义与术语图的存储结构图的存储结构单源最短路径问题顶点对之间最短路径拓扑排序关键路径小结,4.1基本定义与术语,基本定义：图的二元组定义：图G由两个集合V和E组成，记为：G=(V,E)其中：V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集有向图还是无向图，顶点数n、边数e和度数之间有如下关系：其中：n为图中的顶点数，e为图中的边数，D(Vi)为图中的第i顶点的度数基本术语：1.路径（Path）在无向图G中，如果存在一个顶点序列vp,vi1,vi2,vim,vq，使得(vp,vi1)，(vi1,vi2)，(vim,vq)都属于E(G)，则称顶点vp到vq存在一条路径（Path）2.简单路径如果一条路径上除vp和vq外，其余顶点均不相同，则称此路径为一条简单路径（这里vp和vq可以相同也可以不同）,简单回路起点和终点都相同的简单路径称为简单回路（Cycle）。有根图和图的根在一个有向图中，如果存在一个顶点v，从v可以到达图中其他所有顶点，则称此有向图为有根图，其中v称作图的根。连通图和连通分量在无向图中，如果从顶点V到顶点V有路径，则称V和V是连通的。如果对于图中的任意两个顶点Vi和Vj都是连通的，则称G为连通图强连通图和强连通分量在有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。有向图的极大强连通子图称为G的强连通分量。欧拉图如果图中存在一条通过图中每条边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图称为欧拉图8.哈密顿图若图G中存在一条通过图中所有顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图,4.2图的存储结构,4.2.1图的邻接矩阵表示法1.图的邻接矩阵表示法在图的邻接矩阵表示法中，用一个顺序表来存储顶点信息，用邻接矩阵来表示顶点间的相邻关系。2.邻接矩阵（AdacencyMatrix）设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是一个n阶方阵：,4.2.2邻接表表示法,4.2.2邻接表表示法,图的邻接表表示法类似于树的孩子链表表示法邻接表的类型定义如下：#defineMaxVerNum100/最大顶点数为100typedefstructnode/边表结点intadjvex;/邻接点域structnode*next;/链域/若要表示边上的权，则应增加一个数据域EdgeNode;typedefstructvnode/顶点表结点VertexTypevertex;/顶点域EdgeNode*firstedge;/边表头指针VertexNode;typedefVertexNodeAdjListMaxVertexNum;/AdjList是邻接表类型typedefstructAdjListadjlist;/邻接表intn,e;图中当前顶点数和边数ALGraph;/对于简单的应用，无须定义此类型，可直接使用AdjList类型,4.3图的遍历,图的遍历基本方法有两种：深度优先搜索和广度优先搜索，这两种方法都适用于有向图和无向图的遍历4.3.1深度优先搜索特点：尽可能先对纵深方向进行搜索。基本思想是：以图中某个顶点v1为出发点，先访问v1，然后选一个v1的邻接点v2，以v2为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。搜索过程：,4.3.2广度优先搜索,特点：尽可能优先对横向搜索基本思想是：从图中某个顶点v1出发，访问了v1之后依次访问v1的所有邻接点；然后分别从这些邻接点出发按深度优先搜索遍历图的其他顶点，直至所有顶点都被访问到广度优先搜索的过程：,4.4单源最短路径问题,单源最短路径问题是：给定带权有向图G=(V,E)和源点sV，找出从源点s到V中其他各顶点的最短路径迪杰斯特拉（Dijkstra）算法求单源最短路径Dijkstra算法如下所示：Dijkstra(G,D,s)/用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度/以下是初始化操作S=s;Ds=0;/设置初始的红点集及最短距离for(alliV-S)do/对蓝点集中每个顶点iDi=Gsi;/设置i初始的估计距离为w/以下是扩充红点集for(i=0;iDk+Gkj)/新红点k使原Dj值变小时，用新路径的长度修改Dj，使j离s更近Dj=Dk+Gkj;,4.5顶点对之间最短路径,为了求出每一对顶点之间的最短路径，可以应用dijkstra算法，分别以每个顶点为源点，求出从源点到各个顶点最短路径，除此之外，还可以应用另一种算法，称为floyd算法floyd算法的具体过程如下：voidFloeyd(adjmatrixG,adjmatrixd,intn)/利用弗洛伊德算法求图GA每对顶点间的最短长度，对应存于二维数组A中inti,j,k;/给二维数组d赋初值，等于邻接矩阵Gfor(i=0;in;i+)for(j=0;jn;j+)dij=Gij;/依次以每个顶点作为中间点，优化数组dfor(k=0;kn;k+)for(i=0;in;i+)for(j=0;jn;j+)if(i=k|j=k|i=j)continue;if(dik+dkjadjvex;/对i号顶点的每个邻接点的入度减1if(!(-indegreek)Push(S,k);/若入度减为0，则入栈if（countG.vexnum）returnERROR;elsereturnOK;,4.7关键路径,在带权的有向图中，用顶点表示事件（event），弧表示活动（activity），权表示活动持续的时间。于是，把这样的有向图称为关于边的活动网（ActivityOnEdge），简称AOE网，与此相对应，用顶点表示活动的先后顺序关系，这样的有向图称为关于顶点的活动网（ActivityOnVertexNetwork），简称AOV网在AOE网中，由于有些活动可以并列进行，所以，完成工程最少时间是从起始点到结束点最长路径的长度（路径的长度指的是这条路径的所有活动持续的时间之和）。把从起点到结束点具有最大长度的路称为关键路径（criticalpath）分析关键路径的目的是识别哪些活动是关键活动，以便提高关键活动的工效，缩短整个工程的完成时间,小结,图结构是一种比树形结构更复杂的非线性结构。本章介绍了图的概念，图的存储结构，图的深度优先搜索和广度优先搜索算法，以及有向图的若干应用。本章首先介绍了图的基本概念及术语，然后介绍了图的两种存储结构（邻接矩阵和邻接表）的表示方法；接着