数据结构与算法-辛运帏-(5)课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构与算法-辛运帏-(5)课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 辛运帏 课件
- 资源描述:
-
1、第第6章章 图图 6.1 6.1 图的基本概念图的基本概念 6.2 6.2 图的存储结构图的存储结构 6.3 6.3 图的遍历及求图的连通分量图的遍历及求图的连通分量 6.4 6.4 生成树和最小(代价)生成树生成树和最小(代价)生成树 6.5 6.5 最短路径最短路径6.6 6.6 有向无环图及其应用有向无环图及其应用 6.1.1 图的基本概念图的基本概念图(图(graph)图(图(graph)包含两部分,一部分是)包含两部分,一部分是顶点顶点,一,一部分是部分是边边。一般地,图用。一般地,图用G=(V,E)来表示,其中来表示,其中V是顶点(是顶点(vertex)集,一般为一个有穷非空集合;
2、)集,一般为一个有穷非空集合;E是边(是边(edge)集,)集,E中的每条边都是中的每条边都是V中某一对中某一对顶点的连接。顶点的连接。图图G=(V,E)中,顶点总数记为中,顶点总数记为|V|,边的总数,边的总数记为记为|E|。如果图中边的数目较少(相对于顶点数。如果图中边的数目较少(相对于顶点数来说),这样的图称为来说),这样的图称为稀疏图稀疏图(sparse graph););反之,边数较多的图称为反之,边数较多的图称为密集图密集图(dense graph)或是或是稠密图稠密图。示例示例图图6.1 图的示例图的示例02341(a)0213123415(b)(c)术语术语 图中的边除了有数量
3、之分外,还有方向性。图中的边除了有数量之分外,还有方向性。当图中的边限定为从一个顶点指向另一个顶点时,当图中的边限定为从一个顶点指向另一个顶点时,这样的边称为这样的边称为有向边有向边,否则称为,否则称为无向边无向边。组成有。组成有向边的偶对可以看作是有序的,而组成无向边的向边的偶对可以看作是有序的,而组成无向边的偶对是无序的。含有有向边的图称为偶对是无序的。含有有向边的图称为有向图有向图(directed graph或简写为或简写为digraph)。有向图中)。有向图中的边也称为的边也称为弧弧(arc),若(),若(u,v)E是有向图是有向图G中的一条弧,则中的一条弧,则u称为称为弧尾弧尾(t
4、ail),),v称为称为弧头弧头(head)弧的方向是从)弧的方向是从u指向指向v。如果图中的所有边都是无向边时,这样的图如果图中的所有边都是无向边时,这样的图称为称为无向图无向图(undirected graph或或undigraph)。)。图图G=(V,E)中,一条边所连接的两个顶点互称中,一条边所连接的两个顶点互称为为邻接点邻接点(adjacent)。连接一对邻接点)。连接一对邻接点u、v的边的边称为与顶点称为与顶点u、v相关联(相关联(incident)的边,也可以)的边,也可以说边(说边(u,v)依附于顶点)依附于顶点u和和v。有些应用中,为了表明图中边的某些特性,往有些应用中,为了
5、表明图中边的某些特性,往往给边赋予一个非负值,这个非负值称为往给边赋予一个非负值,这个非负值称为权权(weight),相应的图称为),相应的图称为加权图加权图(weighted graph)或是)或是带权图带权图,也有的称之为,也有的称之为网网(network)。)。为了能明确表示图中的所有顶点,可以让各顶为了能明确表示图中的所有顶点,可以让各顶点带有标号,这样的图称为点带有标号,这样的图称为标号图标号图(labedled graph)。)。有有n个顶点的无向图中,可以证明其边数最多可达个顶点的无向图中,可以证明其边数最多可达n(n-1)/2;有向图中由于边具有方向性,所以可能的最大;有向图中
6、由于边具有方向性,所以可能的最大边数比无向图多了一倍,边数比无向图多了一倍,n个顶点的有向图中最大边数为。个顶点的有向图中最大边数为。包含了所有可能边的图称为包含了所有可能边的图称为完全图完全图(complete graph)。)。图图6.2 完全图示例完全图示例1342(a)4个顶点的无向完全图个顶点的无向完全图132(b)3个顶点的有向完全图个顶点的有向完全图在无向图中,与顶点在无向图中,与顶点v相关联的边的数目称为顶点相关联的边的数目称为顶点的的度度(degree)。例如,图)。例如,图6.1(a)中,顶点中,顶点0的度的度为为2;顶点;顶点1的度为的度为1;在有向图中,顶点的度分为出度
7、和入度。以某顶在有向图中,顶点的度分为出度和入度。以某顶点为弧头的弧的数目,称为该顶点的点为弧头的弧的数目,称为该顶点的入度入度(indegree),以某顶点为弧尾的弧的数目,称),以某顶点为弧尾的弧的数目,称为该顶点的为该顶点的出度出度(outdegree)。一个顶点的出度)。一个顶点的出度和入度之和入度之和和称为该顶点的称为该顶点的度度。例如,图。例如,图6.1(b)中,中,顶点顶点0的出度为的出度为2,入度为,入度为0,度为,度为2 假设图假设图G=(V,E)中含有中含有n个顶点,个顶点,e条边,每个条边,每个顶点的度为顶点的度为di(0i2(n-1),则三者之间的关系为:,则三者之间的
8、关系为:(6.1)若两个图若两个图G=(V,E)和和G=(V,E),满足下列条件:,满足下列条件:且且E中边依附的顶点均属于中边依附的顶点均属于V,则称,则称G为为G的的子图子图(subgraph)。)。1021niideEE V,V 图图6.3 子图示例子图示例023410234103410234023410341(a)图图G(b)(c)(d)(e)(f)在图在图G=(V,E)中,如果中,如果(v0,v1),(v1,v2),(vn-2,vn-1)都是都是E中的边,则顶点序列(中的边,则顶点序列(v0,v1,vn-1)称为从顶点)称为从顶点v0到顶到顶点点vn-1的的路径路径(path)。若图
9、)。若图G是有向图,则路径也是有向是有向图,则路径也是有向的,它由的,它由E中的弧中的弧(v0,v1),(v1,v2),(vn-2,vn-1)组成。有组成。有向路径要求所有弧的方向都一致。一条路径上包含的边或向路径要求所有弧的方向都一致。一条路径上包含的边或弧的数目称为弧的数目称为路径长度路径长度(length)。如果路径上各顶点均)。如果路径上各顶点均不同,则称此路径为不同,则称此路径为简单路径简单路径(simple path)。第一个顶)。第一个顶点和最后一个顶点相同的路径称为点和最后一个顶点相同的路径称为回路回路(cycle),回路也),回路也称为称为环环。如果一个回路中除第一个顶点和最
10、后一个顶点之。如果一个回路中除第一个顶点和最后一个顶点之外,其余顶点均不相同,则称为外,其余顶点均不相同,则称为简单回路简单回路(simple cycle)或或简单环简单环。不带回路的图称为不带回路的图称为无环图无环图。不带回路的有向图则。不带回路的有向图则称为称为有向无环图有向无环图。图图6.4 路径示例路径示例02341对于无向图对于无向图G,如果顶点,如果顶点u和顶点和顶点v之间有路径,之间有路径,则称这两个顶点是则称这两个顶点是连通连通的;如果无向图的;如果无向图G中任中任意一个顶点到其他任意顶点都至少存在一条路意一个顶点到其他任意顶点都至少存在一条路径,也就是说,图中任意两个顶点都是
11、连通的,径,也就是说,图中任意两个顶点都是连通的,则称图则称图G为为连通图连通图(connected graph)。无向)。无向图中的极大连通子图称为图中的极大连通子图称为连通分量连通分量(connected component)。)。有向图有向图G中,如果每对顶点中,如果每对顶点u与与v之间均有一条从之间均有一条从u到到v的有向路的有向路径,则称径,则称G为为强连通图强连通图(strongly connected graph),有向图),有向图的最大强连通子图称为的最大强连通子图称为强连通分量强连通分量;如果对于每对顶点;如果对于每对顶点u和和v,存在顶点序列存在顶点序列v0,v1,vn-1
12、,这里,这里u=v0,v=vn-1,并且,并且(vi,vi+1)E或或(vi+1,vi)E(0in-2),则称图),则称图G为为弱连通图弱连通图(weakly connected graph)。)。图图6.5 有向连通图有向连通图(a)强连通图强连通图(b)弱连通图弱连通图6.1.2 图的抽象数据类型图的抽象数据类型/图,顶点,边的抽象数据类型定义图,顶点,边的抽象数据类型定义/class Graph/图类的抽象数据类型图类的抽象数据类型public:Graph();/构造函数构造函数Graph();/析构函数析构函数int countVtx();/返回图中的顶点数返回图中的顶点数int co
13、untEdge();/返回图中的边数返回图中的边数int first_adj(int v);/得到顶点得到顶点v的第一个邻接顶点的第一个邻接顶点int next_adj(int v1,int v2);/得到顶点得到顶点v1在邻接点在邻接点v2之后的下一个之后的下一个邻接点邻接点EdgeweightType weight(Edge e);/返回边返回边e的权值的权值EdgeweightType weight(int v1,int v2);/返回边返回边的权值的权值;class Vertex/顶点类的抽象数据类型顶点类的抽象数据类型public:Vertex();/构造函数构造函数Vertex()
14、;/析构函数析构函数VtxdataType VtxData;/顶点数据顶点数据;class Edge/边类的抽象数据类型边类的抽象数据类型public:Edge();/构造函数构造函数Edge();/析构函数析构函数int adj1;/与边关联的第一个顶点与边关联的第一个顶点int adj2;/与边关联的第二个顶点与边关联的第二个顶点EdgeweightType weight;/该边的权值该边的权值;6.2 图的存储结构图的存储结构 图的结构较复杂,每个图中的顶点数、边数,以图的结构较复杂,每个图中的顶点数、边数,以及每个顶点的度数都可能相差许多。与其他数据及每个顶点的度数都可能相差许多。与其
15、他数据类型类似,图也有两类基本的存储方式,即类型类似,图也有两类基本的存储方式,即顺序顺序存储结构存储结构(或称静态存储结构)及(或称静态存储结构)及动态存储结构动态存储结构。实际应用中可以根据具体的图的特点和对图进行实际应用中可以根据具体的图的特点和对图进行的操作,在这两类基本存储结构之上选取适当的的操作,在这两类基本存储结构之上选取适当的存储结构。存储结构。顺序存储结构以顺序存储结构以邻接矩阵邻接矩阵(adjacency matrix)为)为代表,动态存储结构以代表,动态存储结构以邻接表邻接表(adjacency list)为代表,另外在邻接表基础上,还有逆邻接表及为代表,另外在邻接表基础
16、上,还有逆邻接表及邻接多重表等存储方式。邻接多重表等存储方式。6.2.1 邻接矩阵邻接矩阵设图设图G=(V,E),|V|=n,则图的,则图的邻接矩阵邻接矩阵是一个是一个n*n 矩阵,矩阵元素表示图中各顶点之间的邻接关矩阵,矩阵元素表示图中各顶点之间的邻接关系。邻接矩阵也称为系。邻接矩阵也称为相邻矩阵相邻矩阵。设各顶点依次记为。设各顶点依次记为v0,v1,vn-1,如果从,如果从vi到到vj存在一条边,则邻接矩存在一条边,则邻接矩阵的第阵的第i行第行第j列的元素值为列的元素值为1,否则值为,否则值为0。邻接矩。邻接矩阵的存储空间与顶点个数有关,为阵的存储空间与顶点个数有关,为 O(|V|2)。定
17、义邻接矩阵如下,它是一个二维数组:定义邻接矩阵如下,它是一个二维数组:(6.2)1-nji,0 ,01-nji,0 ,1EvvEvvjiAjiji若若若若对于加权图,如果图中从对于加权图,如果图中从vi到到vj存在一条边,则邻存在一条边,则邻接矩阵的第接矩阵的第i行第行第j列的元素值为边列的元素值为边(vi,vj)的的权权wij,否则值为否则值为。(6.3)1-nji,0 ,1-nji,0 ,EvvEvvwjiAjijiji若若若若例例 加权图加权图G如图如图6.6所示,写出其邻接矩阵表示。所示,写出其邻接矩阵表示。图图6.6 加权图加权图G图图6.6的邻接矩阵如下:的邻接矩阵如下:35v1v
18、2V0v3v427988 29288935837857对于有对于有n个顶点的图个顶点的图G,一般地,其邻接矩阵需要,一般地,其邻接矩阵需要n2个存储位置。考虑到无向图邻接矩阵的个存储位置。考虑到无向图邻接矩阵的对称性对称性,当使用数组存储对称矩阵时,可以只存储其下三当使用数组存储对称矩阵时,可以只存储其下三角(或上三角)的元素;同时,图中不含有角(或上三角)的元素;同时,图中不含有(i,i)形式的边,所以邻接矩阵的对角元素全为形式的边,所以邻接矩阵的对角元素全为0或是或是,也不需要存储。因而无向图的存储空间可压缩到也不需要存储。因而无向图的存储空间可压缩到个个n(n-1)/2存储位置。存储位置
19、。用邻接矩阵表示图时,可以很容易地判定图中任用邻接矩阵表示图时,可以很容易地判定图中任意两顶点之间是否存在意两顶点之间是否存在边边(或弧)。(或弧)。借助于邻接矩阵,也很容易求图中各顶点的借助于邻接矩阵,也很容易求图中各顶点的度度。设用邻接矩阵表示有设用邻接矩阵表示有n个顶点的图个顶点的图G,计算,计算G中有中有多少条边时,需要检查矩阵中的所有元素,因此多少条边时,需要检查矩阵中的所有元素,因此时间复杂度时间复杂度为为O(n2)。另一方面,其。另一方面,其存储空间存储空间仅与仅与图图G中的顶点数有关,与边数无关,即为中的顶点数有关,与边数无关,即为O(n2)。因此,当图中边的数目远远小于因此,
20、当图中边的数目远远小于n2时,检查图中时,检查图中边的数目的时间复杂度及存储邻接矩阵的空间复边的数目的时间复杂度及存储邻接矩阵的空间复杂度都将有极大的浪费。为解决这个问题,可以杂度都将有极大的浪费。为解决这个问题,可以采用另外一种存储结构,即采用另外一种存储结构,即邻接表邻接表。6.2.2 邻接表邻接表邻接表邻接表是图的动态表示方法,它使用链表存储图是图的动态表示方法,它使用链表存储图中顶点的邻接点,每个顶点的所有邻接点存储在中顶点的邻接点,每个顶点的所有邻接点存储在一个链表中,而这些链表的表头又分别存储在一一个链表中,而这些链表的表头又分别存储在一个数组的各元素中。个数组的各元素中。设图设图
21、G=(V,E),则邻接表由一个,则邻接表由一个一维数组一维数组和和|V|个个链表链表组成,邻接表数组包含组成,邻接表数组包含|V|个元素;与顶点个元素;与顶点vi(0in-1)相邻接的所有顶点组成第)相邻接的所有顶点组成第i个链表,其个链表,其表头指针存于一维数组的第表头指针存于一维数组的第i个元素中。除指向链个元素中。除指向链表的指针外,数组元素中还可以保存相应顶点的表的指针外,数组元素中还可以保存相应顶点的相关信息。相关信息。链表的每个结点有两个域,一个是链表的每个结点有两个域,一个是顶点域顶点域,存储,存储邻接顶点在数组中的序号;另一个是邻接顶点在数组中的序号;另一个是指针域指针域,指,
22、指向下一个邻接顶点。向下一个邻接顶点。邻接表的邻接表的表结点结构表结点结构如下图所示:如下图所示:顶点序号顶点序号指针指针例例 以图以图6.1(a)为例,给出它的邻接表为例,给出它的邻接表 图图6.7 邻接表示例邻接表示例2340304241230123401234对于对于带权图带权图,可以让每个链表元素增加一个域,可以让每个链表元素增加一个域,存储两个顶点连成的这条边的权。它的表结点结存储两个顶点连成的这条边的权。它的表结点结构如下所示:构如下所示:例例 图图6.6的邻接表如图的邻接表如图6.8所示:所示:图图6.8 带权图带权图邻接表示例邻接表示例顶点序号顶点序号权值权值指针指针v00v1
23、1v22v33v441738250738230549130842182932对于无向图,使用邻接表可以很方便地求出顶点对于无向图,使用邻接表可以很方便地求出顶点的度,第的度,第i个单链表中个单链表中结点的个数结点的个数即为顶点即为顶点vi的的度度。对于有向图,第对于有向图,第i个单链表中结点的个数为顶点个单链表中结点的个数为顶点vi的的出度出度;如果要计算顶点;如果要计算顶点vi的的入度入度,需要遍历邻接,需要遍历邻接表中的所有表中的所有n个单链表,找出顶点为个单链表,找出顶点为vi的结点个数。的结点个数。用邻接表表示有用邻接表表示有n个顶点和个顶点和e条边的无向图时,需条边的无向图时,需要一
24、个由要一个由n个元素组成的顺序表(表头结点表)个元素组成的顺序表(表头结点表)和和2e个结点组成的个结点组成的n个单链表。而表示有个单链表。而表示有n个顶点个顶点e条弧的有向图时,需要一个由条弧的有向图时,需要一个由n个元素组成的顺个元素组成的顺序表和序表和e个结点组成的个结点组成的n个单链表。邻接表的空间个单链表。邻接表的空间复杂度为复杂度为O(n+e)。使用邻接表存储方式时,判定两个顶点间是否使用邻接表存储方式时,判定两个顶点间是否存存在边在边的操作将比使用邻接矩阵费时,此时需要遍的操作将比使用邻接矩阵费时,此时需要遍历邻接表中的一个单链表。历邻接表中的一个单链表。6.2.3 逆邻接表逆邻
25、接表使用邻接表表示有向图时,求某个顶点的入度比使用邻接表表示有向图时,求某个顶点的入度比计算顶点的出度要麻烦,为此,可以仿效邻接表计算顶点的出度要麻烦,为此,可以仿效邻接表建立有向图的建立有向图的逆邻接表逆邻接表,即把所有邻接到顶点,即把所有邻接到顶点vi 的顶点链接成一个单链表,此时,逆邻接表中第的顶点链接成一个单链表,此时,逆邻接表中第i个单链表中结点的个数即是顶点个单链表中结点的个数即是顶点vi 的入度。的入度。例例 图图6.1(b)的逆邻接表如图的逆邻接表如图6.9所示:所示:图图6.9 逆邻接表示例逆邻接表示例012012012234031156.2.4 邻接多重表邻接多重表在邻接表
展开阅读全文