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

《《图及有向图的应用》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图及有向图的应用》PPT课件.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4章章 图及有向图的应用图及有向图的应用u基本定义与术语基本定义与术语 u图的存储结构图的存储结构 u图的存储结构图的存储结构 u单源最短路径问题单源最短路径问题 u顶点对之间最短路径顶点对之间最短路径 u拓扑排序拓扑排序 u关键路径关键路径 u小结小结小结小结4.1 基本定义与术语基本定义与术语基本定义：基本定义：图的二元组定义：图图的二元组定义：图GG由两个集合由两个集合V V和和E E组成，记为：组成，记为：G=(V,E)G=(V,E)其中：其中：V V是顶点的有穷非空集合，是顶点的有穷非空集合，E E是是V V中顶点偶对（称为边）的有穷集中顶点偶对（称为边）的有穷集 有向图还是无向

2、图，顶点数有向图还是无向图，顶点数n n、边数、边数e e和度数之间有如下关系：和度数之间有如下关系：其中：其中：n n为图中的顶点数，为图中的顶点数，e e为图中的边数，为图中的边数，D(Vi)D(Vi)为图中的第为图中的第i i顶点的度数顶点的度数 基本术语：基本术语：1.1.路路路路径径径径（PathPath）在在无无向向图图GG中中，如如果果存存在在一一个个顶顶点点序序列列vp,vp,vi1,vi1,vi2,vi2,vim,vim,vqvq，使使得得(vp,(vp,vi1)vi1)，(vi1,vi2)(vi1,vi2)，(vim,vq)(vim,vq)都属于都属于E(G)E(G)，则称

3、顶点，则称顶点vpvp到到vqvq存在一条路径（存在一条路径（PathPath）2.2.简简简简单单单单路路路路径径径径 如如如如果果果果一一一一条条条条路路路路径径径径上上上上除除除除vpvp和和和和vqvq外外外外，其其其其余余余余顶顶顶顶点点点点均均均均不不不不相相相相同同同同，则则则则称称称称此此此此路路路路径径径径为为为为一一一一条条条条简简简简单单单单路路路路径（这里径（这里径（这里径（这里vpvp和和和和vqvq可以相同也可以不同）可以相同也可以不同）可以相同也可以不同）可以相同也可以不同）3.3.简单回路简单回路 起点和终点都相同的简单路径称为简单回路（起点和终点都相同的简单路

4、径称为简单回路（CycleCycle）。）。4.4.有根图和图的根有根图和图的根 在一个有向图中，如果存在一个顶点在一个有向图中，如果存在一个顶点v v，从，从v v可以到达图中可以到达图中其他所有顶点，则称此有向图为有根图，其中其他所有顶点，则称此有向图为有根图，其中v v称作图的根。称作图的根。5.5.连通图和连通分量连通图和连通分量 在无向图中，如果从顶点在无向图中，如果从顶点V V到顶点到顶点VV有路径，则称有路径，则称V V和和VV是连通的。如果对于图中的任意两个顶点是连通的。如果对于图中的任意两个顶点ViVi和和VjVj都是连通的，则称都是连通的，则称GG为连通图为连通图 6.6.

5、强连通图和强连通分量强连通图和强连通分量 在有向图在有向图GG中，若对于中，若对于V(G)V(G)中任意两个不同中任意两个不同的顶点的顶点vi vi和和vj vj，都存在从，都存在从vi vi到到vj vj以及从以及从vj vj到到vi vi的路径，则称的路径，则称GG是强连通图。是强连通图。有向图的极大强连通子图称为有向图的极大强连通子图称为GG的强连通分量。的强连通分量。7.7.欧拉图欧拉图 如果图中存在一条通过图中每条边一次且仅一次的回路，则如果图中存在一条通过图中每条边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图称为欧拉图称此回路为欧拉回路，具有欧拉回路的图称为欧拉图8.

6、8.8.8.哈密顿图哈密顿图 若图若图GG中存在一条通过图中所有顶点一次且仅一次的回路，中存在一条通过图中所有顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图 4.2 图的存储结构图的存储结构4.2.1 4.2.1 图的邻接矩阵表示法图的邻接矩阵表示法图的邻接矩阵表示法图的邻接矩阵表示法1.1.图的邻接矩阵表示法图的邻接矩阵表示法图的邻接矩阵表示法图的邻接矩阵表示法在图的邻接矩阵表示法中，用一个顺序表来存储顶点信息，用邻接矩阵来表示顶点间的相邻关在图的邻接矩阵表示法中，用一个顺序表来存储顶点信息，用邻接

7、矩阵来表示顶点间的相邻关系。系。2.2.邻接矩阵（邻接矩阵（邻接矩阵（邻接矩阵（Adacency MatrixAdacency Matrix）设设G=(V,E)G=(V,E)是具有是具有n n个顶点的图，则个顶点的图，则GG的邻接矩阵是一个的邻接矩阵是一个n n阶方阵：阶方阵：4.2.2 邻接表表示法邻接表表示法4.2.2 邻接表表示法邻接表表示法图的邻接表表示法类似于树的孩子链表表示法图的邻接表表示法类似于树的孩子链表表示法 邻接表的类型定义如下：邻接表的类型定义如下：#define MaxVerNum 100#define MaxVerNum 100 /最大顶点数为最大顶点数为100100

8、typedef struct nodetypedef struct node /边表结点边表结点 int adjvex;int adjvex;/邻接点域邻接点域 struct node*next;struct node*next;/链域链域 /若要表示边上的权，则应增加一个数据域若要表示边上的权，则应增加一个数据域EdgeNode;EdgeNode;typedef struct vnode typedef struct vnode /顶点表结点顶点表结点 VertexType vertex;VertexType vertex;/顶点域顶点域 EdgeNode*firstedge;EdgeNod

9、e*firstedge;/边表头指针边表头指针 VertexNode;VertexNode;typedef VertexNode AdjListMaxVertexNum;typedef VertexNode AdjListMaxVertexNum;/AdjList/AdjList是邻接表类型是邻接表类型 typedef struct typedef struct AdjList adjlist;AdjList adjlist;/邻接表邻接表 int n,e;int n,e;图中当前顶点数和边数图中当前顶点数和边数 ALGraph;ALGraph;/对于简单的应用，无须定义此类型，可直接使用对于

10、简单的应用，无须定义此类型，可直接使用AdjListAdjList类型类型4.3 图的遍历图的遍历 图的遍历基本方法有两种：深度优先搜索和广度优先搜索，这两种图的遍历基本方法有两种：深度优先搜索和广度优先搜索，这两种方法都适用于有向图和无向图的遍历方法都适用于有向图和无向图的遍历 4.3.1 4.3.1 深度优先搜索深度优先搜索深度优先搜索深度优先搜索 特点：尽可能先对纵深方向进行搜索。特点：尽可能先对纵深方向进行搜索。基本思想是：以图中某个顶点基本思想是：以图中某个顶点v1v1为出发点，先访问为出发点，先访问v1v1，然后选一个，然后选一个v1v1的邻的邻接点接点v2v2，以，以v2v2为新

11、的出发点继续进行深度优先搜索，直至图中所有顶点都被访为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。问过。搜索过程搜索过程：4.3.2 4.3.2 广度优先搜索广度优先搜索广度优先搜索广度优先搜索特点：尽可能优先对横向搜索特点：尽可能优先对横向搜索 基本思想是：从图中某个顶点基本思想是：从图中某个顶点v1v1出发，访问了出发，访问了v1v1之后依次访问之后依次访问v1v1的所有邻接点；然的所有邻接点；然后分别从这些邻接点出发按深度优先搜索遍历图的其他顶点，直至所有顶点都被后分别从这些邻接点出发按深度优先搜索遍历图的其他顶点，直至所有顶点都被访问到访问到 广度优先搜索的过程广度优先

12、搜索的过程：4.4 单源最短路径问题单源最短路径问题 单源最短路径问题是：给定带权有向图单源最短路径问题是：给定带权有向图G=(V,E)G=(V,E)和源点和源点s sV V，找出从源点，找出从源点s s到到V V中其他各顶点的最短路径中其他各顶点的最短路径 迪杰斯特拉（迪杰斯特拉（DijkstraDijkstra）算法求单源最短路径）算法求单源最短路径 DijkstraDijkstra算法如下所示：算法如下所示：Dijkstra(G,D,s)Dijkstra(G,D,s)/用用DijkstraDijkstra算法求有向网算法求有向网GG的源点的源点s s到各顶点的最短路径长度到各顶点的最短路

13、径长度 /以下是初始化操作以下是初始化操作 S=s;Ds=0;S=s;Ds=0;/设置初始的红点集及最短距离设置初始的红点集及最短距离 for(all i for(all i V-S)do V-S)do /对蓝点集中每个顶点对蓝点集中每个顶点i i Di=Gsi;Di=Gsi;/设置设置i i初始的估计距离为初始的估计距离为wswi /以下是扩充红点集以下是扩充红点集 for(i=0;in-1;i+)do for(i=0;iDk+Gkj)if(DjDk+Gkj)/新红点新红点k k使原使原DjDj值变小时，用新路径的长度修改值变小时，用新路径的长度修改DjDj，使，使j j离离s s更近更近

14、Dj=Dk+Gkj;Dj=Dk+Gkj;4.5 顶点对之间最短路径顶点对之间最短路径 为了求出每一对顶点之间的最短路径，可以应用为了求出每一对顶点之间的最短路径，可以应用dijkstradijkstra算法，分别以每算法，分别以每个顶点为源点，求出从源点到各个顶点最短路径，除此之外，还可以应个顶点为源点，求出从源点到各个顶点最短路径，除此之外，还可以应用另一种算法，称为用另一种算法，称为floydfloyd算法算法 floydfloyd算法的具体过程如下算法的具体过程如下 ：void Floeyd(adjmatrix G,adjmatrix d,int n)void Floeyd(adjmat

15、rix G,adjmatrix d,int n)/利用弗洛伊德算法求图利用弗洛伊德算法求图GAGA每对顶点间的最短长度，对应存于二维数组每对顶点间的最短长度，对应存于二维数组A A中中 int i,j,k;int i,j,k;/给二维数组给二维数组d d赋初值，等于邻接矩阵赋初值，等于邻接矩阵GG for(i=0;in;i+)for(i=0;in;i+)for(j=0;jn;j+)for(j=0;jn;j+)dij=Gij;dij=Gij;/依次以每个顶点作为中间点，优化数组依次以每个顶点作为中间点，优化数组d d for(k=0;kn;k+)for(k=0;kn;k+)for(i=0;in;

16、i+)for(i=0;in;i+)for(j=0;jn;j+)for(j=0;jn;j+)if(i=k|j=k|i=j)if(i=k|j=k|i=j)continue;continue;if(dik+dkjdij)if(dik+dkjdij)dij=dik+dkj;dij=dik+dkj;4.6 拓扑排序拓扑排序 性序列称为满足拓扑次序（性序列称为满足拓扑次序（TopoiSical OrderTopoiSical Order）的序列，简称拓扑序列）的序列，简称拓扑序列 有向图拓扑排序算法的一般步骤如下：有向图拓扑排序算法的一般步骤如下：（1 1）从图中选择一个入度为）从图中选择一个入度为0 0

17、的顶点，输出该顶点。的顶点，输出该顶点。（2 2）从图中删除该顶点及其相关联的弧。）从图中删除该顶点及其相关联的弧。（3 3）重复执行（）重复执行（1 1）、（）、（2 2）直到所有顶点均被输出，或者图中再也没有入度为）直到所有顶点均被输出，或者图中再也没有入度为0 0的的顶点（此种情况说明原有向图含有环）顶点（此种情况说明原有向图含有环）拓扑排序算法如下拓扑排序算法如下：Status TopologicalSort(ALGraph G)Status TopologicalSort(ALGraph G)/有向图有向图GG采用邻接表存储结构采用邻接表存储结构 /若若GG无回路，则输出无回路，则输

18、出GG的顶点的一个拓扑序列并返回的顶点的一个拓扑序列并返回OKOK，否则，否则ERRORERROR FindInDegree(G,indegree);FindInDegree(G,indegree);InitStack(S);InitStack(S);for(i=0;iG.vexnum;i+)for(i=0;inextarc)for(p=G.verticesi.fristarc;p;p=p-nextarc)k=p-adjvex;k=p-adjvex;/对对i i号顶点的每个邻接点的入度减号顶点的每个邻接点的入度减1 1 if(!(-indegreek)Push(S,k);if(!(-indeg

19、reek)Push(S,k);/若入度减为若入度减为0 0，则入栈，则入栈 if if（countcount）return ERROR;return ERROR;else return OK;else return OK;4.7 关键路径关键路径 在带权的有向图中，用顶点表示事件（在带权的有向图中，用顶点表示事件（eventevent），弧表示活动（），弧表示活动（activityactivity），），权表示活动持续的时间。于是，把这样的有向图称为关于边的活动网（权表示活动持续的时间。于是，把这样的有向图称为关于边的活动网（Activity Activity On EdgeOn Edge），

20、简称），简称AOEAOE网，与此相对应，用顶点表示活动的先后顺序关系，这样网，与此相对应，用顶点表示活动的先后顺序关系，这样的有向图称为关于顶点的活动网（的有向图称为关于顶点的活动网（Activity On Vertex NetworkActivity On Vertex Network），简称），简称AOVAOV网网 在在AOEAOE网中，由于有些活动可以并列进行，所以，完成工程最少时间是从起网中，由于有些活动可以并列进行，所以，完成工程最少时间是从起始点到结束点最长路径的长度（路径的长度指的是这条路径的所有活动持续的时始点到结束点最长路径的长度（路径的长度指的是这条路径的所有活动持续的时间

21、之和）。把从起点到结束点具有最大长度的路称为关键路径（间之和）。把从起点到结束点具有最大长度的路称为关键路径（critical pathcritical path）分析关键路径的目的是识别哪些活动是关键活动，以便提高关键活动的工分析关键路径的目的是识别哪些活动是关键活动，以便提高关键活动的工效，缩短整个工程的完成时间效，缩短整个工程的完成时间 小结小结 图结构是一种比树形结构更复杂的非线性结构。图结构是一种比树形结构更复杂的非线性结构。本章介绍了图的概念，图的存储结构，图的深度优本章介绍了图的概念，图的存储结构，图的深度优先搜索和广度优先搜索算法，以及有向图的若干应先搜索和广度优先搜索算法，以

22、及有向图的若干应用。用。本章首先介绍了图的基本概念及术语，然后介本章首先介绍了图的基本概念及术语，然后介绍了图的两种存储结构（邻接矩阵和邻接表）的表绍了图的两种存储结构（邻接矩阵和邻接表）的表示方法；接着引出图的两种遍历（深度优先搜索遍示方法；接着引出图的两种遍历（深度优先搜索遍历和广度优先搜索遍历）的算法思想、步骤，并举历和广度优先搜索遍历）的算法思想、步骤，并举了在两种存储结构上按上述两种遍历算法得到的序了在两种存储结构上按上述两种遍历算法得到的序列；最后说明了几种有向图的应用实例。其中包括：列；最后说明了几种有向图的应用实例。其中包括：最小生成树的概念和按构造最小生成树的几种方法；最小生成树的概念和按构造最小生成树的几种方法；拓扑排序的算法思想及可拓扑排序的基本条件和关拓扑排序的算法思想及可拓扑排序的基本条件和关键路径的定义和构造算法等。键路径的定义和构造算法等。