《图及有向图的应用》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. 邻接矩阵（Adacency Matrix） 设G=(V, E)是具有n个顶点的图，则G的邻接矩阵是一个n阶方阵：,4.2.2 邻接表表示法,4.2.2 邻接表表示法,图的邻接表表示法类似于树的孩子链表表示法 邻接表的类型定义如下： #define MaxVerNum 100 /最大顶点数为100 typedef struct node /边表结点 int adjvex; /邻接点域 struct node *next; /链域 /若要表示边上的权，则应增加一个数据域 EdgeNode; typedef struct vnode /顶点表结点 VertexType vertex; /顶点域 EdgeNode *firstedge; /边表头指针 VertexNode; typedef VertexNode AdjListMaxVertexNum; /AdjList是邻接表类型 typedef struct AdjList adjlist; /邻接表 int n,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( all i V-S )do /对蓝点集中每个顶点i Di=Gsi; /设置i初始的估计距离为w /以下是扩充红点集 for(i=0;iDk+Gkj) /新红点k使原Dj值变小时，用新路径的长度修改Dj，使j离s更近 Dj=Dk+Gkj; ,4.5 顶点对之间最短路径,为了求出每一对顶点之间的最短路径，可以应用dijkstra算法，分别以每个顶点为源点，求出从源点到各个顶点最短路径，除此之外，还可以应用另一种算法，称为floyd算法 floyd算法的具体过程如下 ： void Floeyd(adjmatrix G,adjmatrix d,int n) /利用弗洛伊德算法求图GA每对顶点间的最短长度，对应存于二维数组A中 int i,j,k; /给二维数组d赋初值，等于邻接矩阵G for(i=0;in;i+) for(j=0;jn;j+) dij=Gij; /依次以每个顶点作为中间点，优化数组d for(k=0;kn;k+) for(i=0;in;i+) for(j=0;jn;j+) if(i=k | j=k | i=j) continue; if(dik+dkjdij) dij =dik+dkj; ,4.6 拓扑排序,性序列称为满足拓扑次序（TopoiSical Order）的序列，简称拓扑序列 有向图拓扑排序算法的一般步骤如下： （1）从图中选择一个入度为0的顶点，输出该顶点。 （2）从图中删除该顶点及其相关联的弧。 （3）重复执行（1）、（2）直到所有顶点均被输出，或者图中再也没有入度为0的顶点（此种情况说明原有向图含有环）,拓扑排序算法如下： Status TopologicalSort(ALGraph G) /有向图G采用邻接表存储结构 /若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR FindInDegree(G,indegree); InitStack(S); for(i=0;inextarc) k=p-adjvex; /对i号顶点的每个邻接点的入度减1 if(!(-indegreek) Push(S,k); /若入度减为0，则入栈 if（countG.vexnum） return ERROR; else return OK; ,4.7 关键路径,在带权的有向图中，用顶点表示事件（event），弧表示活动（activity），权表示活动持续的时间。于是，把这样的有向图称为关于边的活动网（Activity On Edge），简称AOE网，与此相对应，用顶点表示活动的先后顺序关系，这样的有向图称为关于顶点的活动网（Activity On Vertex Network），简称AOV网 在AOE网中，由于有些活动可以并列进行，所以，完成工程最少时间是从起始点到结束点最长路径的长度（路径的长度指的是这条路径的所有活动持续的时间之和）。把从起点到结束点具有最大长度的路称为关键路径（critical path） 分析关键路径的目的是识别哪些活动是关键活动，以便提高关键活动的工效，缩短整个工程的完成时间,小结,图结构是一种比树形结构更复杂的非线性结构。本章介绍了图的概念，图的存储结构，图的深度优先搜索和广度优先搜索算法，以及有向图的若干应用。 本章首先介绍了图的基本概念及术语，然后介绍了