第八章 图精选文档.ppt

上传人:石*** 文档编号:43979001 上传时间:2022-09-20 格式:PPT 页数:38 大小:1.98MB
返回 下载 相关 举报
第八章 图精选文档.ppt_第1页
第1页 / 共38页
第八章 图精选文档.ppt_第2页
第2页 / 共38页
点击查看更多>>
资源描述

《第八章 图精选文档.ppt》由会员分享,可在线阅读,更多相关《第八章 图精选文档.ppt(38页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第八章第八章 图图本讲稿第一页,共三十八页本章主要知识点:本章主要知识点:图的基本概念图的基本概念图的存储结构,主要是邻接矩阵存储结构和邻接图的存储结构,主要是邻接矩阵存储结构和邻接表存表存 储结构储结构图的遍历,主要是深度优先算法和广度优先遍历算图的遍历,主要是深度优先算法和广度优先遍历算法法最小生成树的基本概念,以及普里姆算法和克鲁最小生成树的基本概念,以及普里姆算法和克鲁斯卡尔算法斯卡尔算法最短路径的基本概念,狄克斯特拉算法思想最短路径的基本概念,狄克斯特拉算法思想 本讲稿第二页,共三十八页8.1 概述概述8.1.1 图的基本概念图的基本概念 图图 是由结点集合及结点间的关系集合组成的一

2、种是由结点集合及结点间的关系集合组成的一种数据结构。数据结构。结点和边结点和边 图中的顶点称作结点,图中的第图中的顶点称作结点,图中的第i个结个结点记做点记做vi。本讲稿第三页,共三十八页 有向图有向图 在有向图中,结点对在有向图中,结点对x,y是有序的,是有序的,结点对结点对x,y称为从结点称为从结点x到结点到结点y的一条有向边,的一条有向边,因此,因此,x,y与与y,x是两条不同的边。有向图是两条不同的边。有向图中的结点对中的结点对x,y用一对尖括号括起来,用一对尖括号括起来,x是有向是有向边的始点,边的始点,y是有向边的终点,有向图中的边也是有向边的终点,有向图中的边也称作弧称作弧.本讲

3、稿第四页,共三十八页 无向图无向图 在无向图中,结点对(在无向图中,结点对(x,y)是无序的,)是无序的,结点对(结点对(x,y)称为与结点)称为与结点x和结点和结点y相关联的一条边。相关联的一条边。(x,y)等价于)等价于x,y和和y,x。本讲稿第五页,共三十八页 完全图完全图 在有在有n个结点的无向图中,若有个结点的无向图中,若有n(n-1)/2条条边,即任意两个结点之间有且只有一条边,则称此图边,即任意两个结点之间有且只有一条边,则称此图为无向完全图。在有为无向完全图。在有n个结点的有向图中,若有个结点的有向图中,若有n(n-1)条边,即任意两个结点之间有且只有方向相反的两条条边,即任意

4、两个结点之间有且只有方向相反的两条边,则称此图为有向完全图。边,则称此图为有向完全图。本讲稿第六页,共三十八页 邻接结点邻接结点 在无向图在无向图G中,若(中,若(u,v)是)是E(G)中的中的一条边,则称一条边,则称u和和v互为邻接结点,并称边(互为邻接结点,并称边(u,v)依)依附于结点附于结点u和和v。在有向图在有向图G中,若中,若u,v是是E(G)中中的一条边,则称结点的一条边,则称结点u邻接到结点邻接到结点v,结点,结点v邻接自邻接自结点结点u,并称边,并称边u,v和结点和结点u和结点和结点v相关联。相关联。本讲稿第七页,共三十八页 结点的度结点的度 结点结点v的度是与它相关联的边的

5、条数,的度是与它相关联的边的条数,记作记作TD(v)。路径路径 在图在图G=(V,E)中,若从结点中,若从结点vi出发有一组边出发有一组边使可到达结点使可到达结点vj,则称结点,则称结点vi到结点到结点vj的结点序列的结点序列为从结点为从结点vi到结点到结点vj的路径的路径本讲稿第八页,共三十八页 权权 有些图的边附带有数据信息,这些附带的数据信息有些图的边附带有数据信息,这些附带的数据信息称为权。第称为权。第i条边的权用符号条边的权用符号wi表示。表示。路径长度路径长度 对于不带权的图,一条路径的路径长度是指该对于不带权的图,一条路径的路径长度是指该路径上的边的条数;对于带权的图,一条路径的

6、路径长度是路径上的边的条数;对于带权的图,一条路径的路径长度是指该路径上各个边权值的总指该路径上各个边权值的总和和。本讲稿第九页,共三十八页 子图子图 设有图设有图G1=V1,E1和图和图G2=V2,E2,若,若V2V1且且E2E1,则称图,则称图G2是图是图G1的子图。的子图。连通图和强连通图连通图和强连通图 在无向图中,若从结点在无向图中,若从结点vi到结点到结点vj有路径,有路径,则称结点则称结点vi和结点和结点vj是连通的。如果图中任意一对结点都是连通是连通的。如果图中任意一对结点都是连通的,则称该图是连通图。在有向图中,若对于任意一对结点的,则称该图是连通图。在有向图中,若对于任意一

7、对结点vi和结点和结点vj(vivj)都存在路径,则称图)都存在路径,则称图G是强连通图。是强连通图。本讲稿第十页,共三十八页 生成树生成树 一个连通图的最小连通子图称作该图一个连通图的最小连通子图称作该图的生成树。有的生成树。有n个结点的连通图的生成树有个结点的连通图的生成树有n个结个结点和点和n-1条边。条边。简单路径和回路简单路径和回路 若路径上各结点若路径上各结点v1,v2,vm,互不重复,则称这样的路径为简单路径;若路径上互不重复,则称这样的路径为简单路径;若路径上第一个结点第一个结点v1与最后一个结点与最后一个结点vm重合,则称这样重合,则称这样的路径为回路或环。的路径为回路或环。

8、本讲稿第十一页,共三十八页8.1.2 8.1.2 图的抽象数据类型图的抽象数据类型 数据集合数据集合:由一组结点集合:由一组结点集合vi和一组边和一组边ej集合组成。当为带权图集合组成。当为带权图时每条边上权时每条边上权wj还构成权集合还构成权集合wj。操作集合操作集合:(1)初始化)初始化initiate(n):(2)插入结点)插入结点 insertVertex(vertex):(3)插入边)插入边insertEdge(v1,v2,weight):(4)删除边)删除边deleteEdge(v1,v2):(5)删除结点)删除结点deleteVertex(vertex):(6)第一个邻接结点)第

9、一个邻接结点getFirstVex(v):(7)下一个邻接结点)下一个邻接结点getNextVex(int v1,v2):(8)遍历)遍历depthFirstSearch(vs):本讲稿第十二页,共三十八页8.2 图的存储结构图的存储结构8.2.1 图的邻接矩阵存储结构图的邻接矩阵存储结构 假设图假设图G=(V,E)有有n个结点,即个结点,即V=v0,v1,vn-1,E可用可用如下形式的矩阵如下形式的矩阵A描述,对于描述,对于A中的每一个元素中的每一个元素aij,满,满足:足:由于矩阵由于矩阵A中的元素中的元素aij表示了结点表示了结点vi和结点和结点vj之间边的之间边的关系,或者说,关系,或

10、者说,A中的元素中的元素aij表示了结点表示了结点vi和结点和结点vj(0jn-1)的邻接关系,所以矩阵)的邻接关系,所以矩阵A称作称作邻接矩阵邻接矩阵。本讲稿第十三页,共三十八页无向图及其邻接矩阵无向图及其邻接矩阵 本讲稿第十四页,共三十八页有向图及其邻接矩阵有向图及其邻接矩阵本讲稿第十五页,共三十八页带权图及其邻接矩阵带权图及其邻接矩阵 本讲稿第十六页,共三十八页8.2.2 图的邻接表存储结构图的邻接表存储结构 图的邻接矩阵存储结构的主要特点是把图的边信息存图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个储在一个nn矩阵中,其中矩阵中,其中n为图中的结点个数。为图中的结点个数。有向图

11、的邻接表存储结构有向图的邻接表存储结构 本讲稿第十七页,共三十八页8.3 邻接矩阵图类邻接矩阵图类 1邻接矩阵图类邻接矩阵图类AdjMWGraph的设计的设计2邻接矩阵图类邻接矩阵图类AdjMWGraph的测试的测试 本讲稿第十八页,共三十八页8.4 图的遍历图的遍历 8.4.1 图的深度和广度优先遍历算法图的深度和广度优先遍历算法 图的遍历算法设计需要考虑三个问题:图的遍历算法设计需要考虑三个问题:(1)图的特点是没有首尾之分,所以算法的参数要指)图的特点是没有首尾之分,所以算法的参数要指定访问的第一个结点;定访问的第一个结点;(2)对图的遍历路径有可能构成一个回路,从而造成)对图的遍历路径

12、有可能构成一个回路,从而造成死循环,所以算法设计要考虑遍历路径可能出现的死死循环,所以算法设计要考虑遍历路径可能出现的死循环问题;循环问题;(3)一个结点可能和若干个结点都是邻接结点,要使)一个结点可能和若干个结点都是邻接结点,要使一个结点的所有邻接结点按照某种次序被访问。一个结点的所有邻接结点按照某种次序被访问。本讲稿第十九页,共三十八页1 图的深度优先遍历算法图的深度优先遍历算法 连通图的深度优先遍历递归算法为:连通图的深度优先遍历递归算法为:(1)访问结点)访问结点v并标记结点并标记结点v为已访问;为已访问;(2)查找结点)查找结点v的第一个邻接结点的第一个邻接结点w;(3)若结点)若结

13、点v的邻接结点的邻接结点w存在,则继续执行,否则算法存在,则继续执行,否则算法结束;结束;(4)若结点)若结点w尚未被访问则深度优先搜索递归访问结点尚未被访问则深度优先搜索递归访问结点w;(5)查找结点)查找结点v的的w邻接结点的下一个邻接结点邻接结点的下一个邻接结点w,转到,转到步骤(步骤(3)。)。本讲稿第二十页,共三十八页2 图的广度优先遍历算法图的广度优先遍历算法 连通图的广度优先遍历算法为:连通图的广度优先遍历算法为:(1)访问初始结点)访问初始结点v并标记结点并标记结点v为已访问;为已访问;(2)结点)结点v入队列;入队列;(3)当队列非空时则继续执行,否则算法结束;)当队列非空时

14、则继续执行,否则算法结束;(4)出队列取得队头结点)出队列取得队头结点u;(5)查找结点)查找结点u的第一个邻接结点的第一个邻接结点w;(6)若结点)若结点u的邻接结点的邻接结点w不存在,则转到步骤(不存在,则转到步骤(3),否则循环执行,),否则循环执行,(6.1)若结点)若结点w尚未被访问,则访问结点尚未被访问,则访问结点w,并标记结点,并标记结点w为已访问;为已访问;(6.2)结点)结点w入队列;入队列;(6.3)查找结点)查找结点u的的w邻接结点后的下一个邻接结点邻接结点后的下一个邻接结点w,转到步骤(,转到步骤(6)。)。本讲稿第二十一页,共三十八页3 非连通图的遍历非连通图的遍历

15、对于连通图,从图的任意一个结点开始深度或广度优对于连通图,从图的任意一个结点开始深度或广度优先遍历,一定可以访问图中的所有结点。但对于非连先遍历,一定可以访问图中的所有结点。但对于非连通图,从图的任意一个结点开始深度或广度优先遍历,通图,从图的任意一个结点开始深度或广度优先遍历,并不能访问图中的所有结点。对于非连通图,从图的并不能访问图中的所有结点。对于非连通图,从图的任意一个结点开始深度或广度优先遍历只能访问和初任意一个结点开始深度或广度优先遍历只能访问和初始结点连通的所有结点。始结点连通的所有结点。本讲稿第二十二页,共三十八页8.4.2 图的深度和广度优先遍历成员函数设计图的深度和广度优先

16、遍历成员函数设计1 访问结点访问结点2 深度和广度优先遍历成员函数设计深度和广度优先遍历成员函数设计3 测试程序测试程序本讲稿第二十三页,共三十八页8.5 最小生成树最小生成树8.5.1 最小生成树的基本概念最小生成树的基本概念 一个有一个有n个结点的连通图的个结点的连通图的生成树生成树是原图的极小连通子是原图的极小连通子图,它包含原图中的所有图,它包含原图中的所有n个结点,并且有保持图连通个结点,并且有保持图连通的最少的边。的最少的边。如果无向连通图是一个带权图,那么它的所有生成树如果无向连通图是一个带权图,那么它的所有生成树中必有一棵边的权值总和最小的生成树,我们称这棵中必有一棵边的权值总

17、和最小的生成树,我们称这棵生成树为生成树为最小代价生成树最小代价生成树,简称,简称最小生成树最小生成树。本讲稿第二十四页,共三十八页无向图和它的不同的生成树无向图和它的不同的生成树 本讲稿第二十五页,共三十八页 从最小生成树的定义可知,构造有从最小生成树的定义可知,构造有n个结点的无向连通个结点的无向连通带权图的最小生成树带权图的最小生成树,必须满足以下三条:必须满足以下三条:(1)构造的最小生成树必须包括)构造的最小生成树必须包括n个结点;个结点;(2)构造的最小生成树中有且只有)构造的最小生成树中有且只有n-1条边;条边;(3)构造的最小生成树中不存在回路。)构造的最小生成树中不存在回路。

18、构造最小生成树的方法有许多种,典型的构造方法有构造最小生成树的方法有许多种,典型的构造方法有两种,一种称作两种,一种称作普里姆普里姆(Prim)算法,另一种称作)算法,另一种称作克克鲁斯卡尔鲁斯卡尔(Kruskal)算法。)算法。本讲稿第二十六页,共三十八页8.5.2普里姆算法普里姆算法1 普里姆算法思想普里姆算法思想 假设假设G=(V,E)为一个带权图,其中为一个带权图,其中V为带权图中结点的集合,为带权图中结点的集合,E为为带权图中边的权值集合。设置两个新的集合带权图中边的权值集合。设置两个新的集合U和和T,其中,其中U用于用于存放带权图存放带权图G的最小生成树的结点的集合,的最小生成树的

19、结点的集合,T用于存放带权图用于存放带权图G的最小生成树的权值的集合。的最小生成树的权值的集合。普里姆算法思想普里姆算法思想是:令集合是:令集合U的初值为的初值为U=u0(即假设构造最小生(即假设构造最小生成树时从结点成树时从结点u0开始),集合开始),集合T的初值为的初值为T=。从所有结点。从所有结点uU和结点和结点vV-U的带权边中选出具有最小权值的边的带权边中选出具有最小权值的边(u,v),将结点,将结点v加入加入集合集合U中,将边中,将边(u,v)加入集合加入集合T中。如此不断重复,当中。如此不断重复,当U=V时则最时则最小生成树构造完毕。此时集合小生成树构造完毕。此时集合U中存放着最

20、小生成树结点的集合,中存放着最小生成树结点的集合,集合集合T中存放着最小生成树边的权值集合。中存放着最小生成树边的权值集合。本讲稿第二十七页,共三十八页普里姆算法构造最小生成树的过程普里姆算法构造最小生成树的过程本讲稿第二十八页,共三十八页2 普里姆函数设计普里姆函数设计 这里我们令当弧头结点等于弧尾结点时权值等于这里我们令当弧头结点等于弧尾结点时权值等于0。函数的参数设计:函数的参数设计:普里姆函数应有两个参数:普里姆函数应有两个参数:一个参数是图一个参数是图g,这里图,这里图g定义为邻接矩阵存储结构图定义为邻接矩阵存储结构图类的对象;类的对象;另一个参数是通过函数得到的最小生成树的结点数据

21、另一个参数是通过函数得到的最小生成树的结点数据和相应结点的边的权值数据和相应结点的边的权值数据closeVertex。本讲稿第二十九页,共三十八页普里姆算法运行时数组普里姆算法运行时数组lowCost的变化过程的变化过程 本讲稿第三十页,共三十八页8.5.3 克鲁斯卡尔算法克鲁斯卡尔算法 克鲁斯卡尔克鲁斯卡尔算法是:设无向连通带权图算法是:设无向连通带权图G=(V,E),其中,其中V为结点为结点的集合,的集合,E为边的集合。设带权图为边的集合。设带权图G的最小生成树的最小生成树T由结点集合和边由结点集合和边的集合构成,其初值为的集合构成,其初值为T=(V,),即初始时最小生成树,即初始时最小生

22、成树T只由带权只由带权图图G中的结点集合组成,各结点之间没有一条边。这样,最小中的结点集合组成,各结点之间没有一条边。这样,最小生成树生成树T中的各个结点各自构成一个连通分量。然后,按照边的权中的各个结点各自构成一个连通分量。然后,按照边的权值递增的顺序考察带权图值递增的顺序考察带权图G中的边集合中的边集合E中的各条边。若被考察的中的各条边。若被考察的边的两个结点属于边的两个结点属于T的两个不同的连通分量,则将此边加入到最小生的两个不同的连通分量,则将此边加入到最小生成树成树T,同时把两个连通分量连接为一个连通分量;若被考察的边的两,同时把两个连通分量连接为一个连通分量;若被考察的边的两个结点

23、属于个结点属于T的同一个连通分量,则将此边舍去。如此下去,当的同一个连通分量,则将此边舍去。如此下去,当T中的连通分量个数为中的连通分量个数为1时,时,T中的该连通分量即为带权图中的该连通分量即为带权图G的的一棵最小生成树。一棵最小生成树。本讲稿第三十一页,共三十八页克鲁斯卡尔算法构造最小生成树的过程克鲁斯卡尔算法构造最小生成树的过程 本讲稿第三十二页,共三十八页 8.6 最短路径最短路径8.6.1 最短路径的基本概念最短路径的基本概念 在一个图中,若从一个结点到另一个结点存在着在一个图中,若从一个结点到另一个结点存在着路径,定义路径,定义路径长度路径长度为一条路径上所经过的边的为一条路径上所

24、经过的边的数目。图中从一个结点到另一个结点可能存在着数目。图中从一个结点到另一个结点可能存在着多条路径,我们把路径长度最短的那条路径叫做多条路径,我们把路径长度最短的那条路径叫做最短路径最短路径,其路径长度叫做,其路径长度叫做最短最短路径路径长度或长度或最短距最短距离离.本讲稿第三十三页,共三十八页 在一个带权图中,若从一个结点到另一个结点存在一个带权图中,若从一个结点到另一个结点存在着一条路径,则称该路径上所经过边的权值之和在着一条路径,则称该路径上所经过边的权值之和为该路径上的为该路径上的带权路径长度带权路径长度。带权图中从一个结点到。带权图中从一个结点到另一个结点可能存在着多条路径,我们

25、把带权路径长另一个结点可能存在着多条路径,我们把带权路径长度值最小的那条路径也叫做度值最小的那条路径也叫做最短路径最短路径,其带权路径,其带权路径长度也叫做长度也叫做最短路径长度最短路径长度或或最短距离最短距离。本讲稿第三十四页,共三十八页8.6.2 从一个点到其余各结点的最点路径从一个点到其余各结点的最点路径 1 狄克斯特拉算法思想狄克斯特拉算法思想 狄克斯特拉算法狄克斯特拉算法是:设置两个结点的集合是:设置两个结点的集合S和和T,集合,集合S中存放已找到最短路径的结点,集合中存放已找到最短路径的结点,集合T中存放当前还未找到中存放当前还未找到最短路径的结点。初始状态时,集合最短路径的结点。

26、初始状态时,集合S中只包含源点,设为中只包含源点,设为v0,然后从集合,然后从集合T中选择到源点中选择到源点v0路径长度最短的结点路径长度最短的结点u加加入到集合入到集合S中,集合中,集合S中每加入一个新的结点中每加入一个新的结点u都要修改源点都要修改源点v0到集合到集合T中剩余结点的当前最短路径长度值,集合中剩余结点的当前最短路径长度值,集合T中各中各结点的新的当前最短路径长度值,为原来的当前最短路径结点的新的当前最短路径长度值,为原来的当前最短路径长度值与从源点过结点长度值与从源点过结点u到达该结点的路径长度中的较小者。到达该结点的路径长度中的较小者。此过程不断重复,直到集合此过程不断重复

27、,直到集合T中的结点全部加入到集合中的结点全部加入到集合S 中中为止。为止。下图为意示例:下图为意示例:本讲稿第三十五页,共三十八页本讲稿第三十六页,共三十八页8.6.3 每对结点之间的最短路径每对结点之间的最短路径 弗洛伊德算法是:设矩阵弗洛伊德算法是:设矩阵cost用来存放带权有向图用来存放带权有向图G的权值,即矩阵元素的权值,即矩阵元素costij中存放着下标为中存放着下标为i的结点到下标为的结点到下标为j的结点之间的权值,可以通过递推的结点之间的权值,可以通过递推构造一个矩阵序列构造一个矩阵序列A0,A1,A2,AN来求每对结点之间的最短路径。初始时有,来求每对结点之间的最短路径。初始

28、时有,A0ij=costij。当已经求出。当已经求出Ak,要递推求解要递推求解Ak+1时,可分两种情况来考虑:时,可分两种情况来考虑:一种情况是该路径不经过下标为一种情况是该路径不经过下标为k+1的结点,此时该路径长度与从结点的结点,此时该路径长度与从结点vi到结点到结点vj的路径上所经过的结点下标不大于的路径上所经过的结点下标不大于k的最短路径长度相同;另一种情的最短路径长度相同;另一种情况是该路径经过下标为况是该路径经过下标为k+1的结点,此时该路径可分为两段,一段是从结的结点,此时该路径可分为两段,一段是从结点点vi到结点到结点vk+1的最短路径,另一段是从结点的最短路径,另一段是从结点

29、vk+1到结点到结点vj的最短路径,此的最短路径,此时的最短路径长度等于这两段最短路径长度之和。这两种情况中的路径长时的最短路径长度等于这两段最短路径长度之和。这两种情况中的路径长度较小者,就是要求的从结点度较小者,就是要求的从结点vi到结点到结点vj的路径上所经过的结点下标不大于的路径上所经过的结点下标不大于k+1的最短路径长度。的最短路径长度。本讲稿第三十七页,共三十八页弗洛伊德算法的算法思想可用如下递推公式描述:弗洛伊德算法的算法思想可用如下递推公式描述:A0ij=costij Ak+1ij=minAkij,Akik+1+Akk+1j (0kn-1)也就是说,初始时,也就是说,初始时,A0ij=costij,然后进行递推,然后进行递推,每递推一次,从结点每递推一次,从结点vi到结点到结点vj的最短路径上就多考虑的最短路径上就多考虑了一个经过的中间结点,这样,经过了一个经过的中间结点,这样,经过n次递推后得到的次递推后得到的Anij就是考虑了经过图中所有结点情况下的从结点就是考虑了经过图中所有结点情况下的从结点vi到结点到结点vj的最短路径长度。的最短路径长度。本讲稿第三十八页,共三十八页

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 大学资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁