零基础学数据结构第10章图.ppt
《零基础学数据结构第10章图.ppt》由会员分享,可在线阅读,更多相关《零基础学数据结构第10章图.ppt(93页珍藏版)》请在咨信网上搜索。
1、第第10章章图图图图(graph)是是一一种种比比线线性性表表、树树更更为为复复杂杂的的数数据据结结构构。在在线线性性表表中中,数数据据元元素素之之间间呈呈线线性性关关系系,即即每每个个元元素素只只有有一一个个直直接接前前驱驱和和一一个个直直接接后后继继。图图的的应应用用领领域域十十分分广广泛泛,如如化化学学分分析析、工工程程设设计计、遗遗传传学学、人人工工智智能能等等。本本章章主主要要介介绍绍图图的的定定义义、图图的的存存储储结结构构、图图的的遍遍历历、最小生成树、关键路径和最短路径。最小生成树、关键路径和最短路径。本章重点:本章重点:1 1、图的定义及性质、图的定义及性质 2 2、图的邻接
2、矩阵和邻接表表示、图的邻接矩阵和邻接表表示 3 3、图的各种遍历、图的各种遍历 4 4、最小生成树、最小生成树 5 5、关键路径、关键路径 6 6、最短路径、最短路径辰枉储哎眼子皱蝴受灸龄蕉级蚁夸咆诫诗铁爸锣恫埠蠕寇妇联柯孜弱笛诗零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念图图G也是由数据元素集合也是由数据元素集合V与边的集合与边的集合E构成的。在图中,数据元构成的。在图中,数据元素通常称为顶点(素通常称为顶点(Vertex)。其中,顶点集合)。其中,顶点集合V不能为空,边表示不能为空,边表示顶点之间的关系。顶点之间的关系。若若E,则,则表示
3、从顶点表示从顶点x到顶点到顶点y存在一条弧存在一条弧(Arc),),x称为弧尾(称为弧尾(tail)或起始点()或起始点(initialnode),),y称为弧称为弧头(头(head)或终端点()或终端点(terminalnode)。这样的图被称为有向图)。这样的图被称为有向图(digraph)。)。如果如果E且有且有E,即,即E是对称的,则用无序对是对称的,则用无序对(x,y)代替有序对代替有序对和和,表示,表示x与与y之间存在一条边之间存在一条边(edge),这样的图称为无向图(),这样的图称为无向图(undigraph)。如图)。如图10.1所示。所示。称副舶恒呻早飘钉券磋玫斗兰党将历唉
4、崔鄙傻垦塑粉酗截箕旷锐裹伍抱垦零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念图图G的形式化定义为:的形式化定义为:G=(V,E),其中,其中,V=x|x数据元素集数据元素集合合,E=|Path(x,y)/(xV,yV)。Path(x,y)表示表示的意义或信息。的意义或信息。在图在图10.1中,有向图中,有向图G1可以表示为可以表示为G1=(V1,E1),其中,顶点的,其中,顶点的集合为集合为V1=a,b,c,d,边的集合为,边的集合为E1=,。无向图。无向图G2可可以表示为以表示为G2=(V2,E2),其中,顶点的集合为,其中,顶点的集合为V2
5、=a,b,c,d,边的集,边的集合为合为E2=(a,b),(a,c),(a,d),(b,c),(c,d)。钧拖毖妆啮魁乓碴眉益焉片练困蓑肪当憾泳享泉梦妮姐渣绘篙所累察傣妮零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念1邻接点邻接点对于无向图对于无向图G=(V,E),若边,若边(vi,vj)E,则称,则称vi和和vj互为邻接点互为邻接点(adjacent),即),即vi和和vj相邻接。边相邻接。边(vi,vj)依附于顶点依附于顶点vi和和vj,或,或者说者说(vi,vj)与顶点与顶点vi、vj相关联。对于有向图相关联。对于有向图G=(V,A),若
6、弧,若弧A,则称顶点,则称顶点vi邻接到顶点邻接到顶点vj,顶点,顶点vj邻接自顶点邻接自顶点vi。弧。弧和顶点和顶点vi、vj相关联。相关联。无向图无向图G2的边的集合为的边的集合为E=(a,b),(a,c),(a,d),(b,c),(c,d),顶点顶点a和和b互为邻接点,边互为邻接点,边(a,b)依附于顶点依附于顶点a和和b。顶点。顶点c和和d互为邻互为邻接点,边接点,边(c,d)依附于顶点依附于顶点c和和d。有向图。有向图G1的弧的集合为的弧的集合为A=,,顶点,顶点a邻接到邻接到顶点顶点b,弧,弧与顶点与顶点a和和b相关联。顶点相关联。顶点c邻接自顶点邻接自顶点d,弧,弧与顶点与顶点d
7、和和c相关联。相关联。抬衣猴影磨垫乍褥糟躲鞘次每泻糊题丘嗡宵俩铂拱您袄案悠戊不置淫佰砸零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念2顶点的度顶点的度对于无向图,顶点对于无向图,顶点v的度是指与的度是指与v相关联的边的数目,记作相关联的边的数目,记作TD(v)。对于。对于有向图,以顶点有向图,以顶点v为弧头的数目称为顶点为弧头的数目称为顶点v的入度的入度(indegree),记作,记作ID(v)。以顶点。以顶点v为弧尾的数目称为为弧尾的数目称为v的出度的出度(outdegree),记作,记作OD(v)。顶点。顶点v的度的度(degree)为为T
8、D(v)=ID(v)+OD(v)。无向图无向图G2中顶点中顶点a的度为的度为3,顶点,顶点b的度为的度为2,顶点,顶点c的度为的度为3,顶点,顶点d的度的度为为2。有向图。有向图G1的弧的集合为的弧的集合为A=,,顶点,顶点a、b、c和和d的入度分别为的入度分别为1、2、2和和1,顶点,顶点a、b、c和和d的出度分别为的出度分别为2、1、2和和1,顶点,顶点a、b、c和和d的度分别为的度分别为3、3、4和和2。若图的顶点的个数为若图的顶点的个数为n,边数或弧数为,边数或弧数为e,顶点,顶点vi的度记作的度记作TD(vi),则顶,则顶点的度与弧或者边数满足关系:点的度与弧或者边数满足关系:e=绞
9、氮籍傍骇商根籽嘉孩辰贞衔蒙聪乘搞学婿彬果滇敦并烤纫爵沥穆碱首虚零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念3路径路径无向图无向图G中,从顶点中,从顶点v到顶点到顶点v的路径(的路径(path)是从)是从v出发,经出发,经过一系列的顶点序列到达顶点过一系列的顶点序列到达顶点v。如果。如果G是有向图,则路径也是有向是有向图,则路径也是有向的,路径的长度是路径上弧或边的数目。第一个顶点和最后一个顶的,路径的长度是路径上弧或边的数目。第一个顶点和最后一个顶点相同的路径称为回路或环(点相同的路径称为回路或环(cycle)。序列中顶点不重复出现的路)。序
10、列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外,其他顶点不径称为简单路径。除了第一个顶点和最后一个顶点外,其他顶点不重复出现的回路,称为简单回路或简单环。重复出现的回路,称为简单回路或简单环。在图在图10.1所示的有向图所示的有向图G1中,顶点序列中,顶点序列adca构成了一构成了一个简单回路。在无向图个简单回路。在无向图G2中,从顶点中,从顶点a到顶点到顶点c所经过的路径为所经过的路径为a,d和和c(或(或a、b、c)。)。妆瓜戴腿屡维陡瘸劳膘以晨弘剖谴皋赌塔街蕴拼颤淳腋瞳啦拧邮橱箍窘泄零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定
11、义与相关概念4子图子图假设存在两个图假设存在两个图G=V,E和和G=V,E,若,若G的顶点和关系都是的顶点和关系都是V的子集,即有的子集,即有VV,EE,则,则G为为G的子图。如图的子图。如图10.2所示。所示。帆蛛欺绎谱惯锚耕越宋希疮酶尤阶春宽稀鲸爽鹤塞味筑毯骏瓤炉组季蜕摸零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念5连通图和强连通图连通图和强连通图对于无向图对于无向图G,如果从顶点,如果从顶点vi到顶点到顶点vj存在路径,则称存在路径,则称vi到到vj是连通是连通的。如果对于图中任意两个顶点的。如果对于图中任意两个顶点vi、vjV,vi和
12、和vj都是连通的,则称都是连通的,则称G是连通图(是连通图(connectedgraph)。无向图中的极大连通子图称为连通)。无向图中的极大连通子图称为连通分量。无向图分量。无向图G3与连通分量如图与连通分量如图10.3所示。所示。蔓秽即瑞茸沟蜡扛货台乏师捷坝文款驰渺栈诵试粒掣宛力邦颓星坏睫阀撤零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念对于有向图对于有向图G,如果对每一对顶点,如果对每一对顶点vi和和vj,且,且vivj,从,从vi到到vj和和vj到到vi都存在路径,则都存在路径,则G为强连通图。有向图中的极大强连通子图称为为强连通图。有向
13、图中的极大强连通子图称为有向图的强连通分量。有向图有向图的强连通分量。有向图G4与强连通分量如图与强连通分量如图10.4所示。所示。啡惦首肌赋累奢蜘园淬局赤楔腻眨钾虏燕代否微纫妆限焊韦帜于继自仓膊零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念6完全图完全图若图的顶点数目是若图的顶点数目是n,图的边(弧)的数目是,图的边(弧)的数目是e。若不存在顶点到。若不存在顶点到自身的边或弧,即若存在自身的边或弧,即若存在,则有,则有vivj。对于无向图,边数。对于无向图,边数e的取值范围为的取值范围为0n(n-1)/2。将具有。将具有n(n-1)/2条边的
14、无向图称为完全条边的无向图称为完全图(图(completedgraph)或无向完全图。对于有向图,弧数)或无向完全图。对于有向图,弧数e的取值的取值范围是范围是0n(n-1)。将具有。将具有n(n-1)条弧的有向图称为有向完全图。条弧的有向图称为有向完全图。宇妒匣柱赘掷种僳捡免汉嫂欢具字喜稚砂崩饮豁册涝疏温怀趁在乏嫡战帜零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念7稀疏图和稠密图稀疏图和稠密图具有具有enlogn条弧或边的图,称为稀疏图。反之,称为稠密图。条弧或边的图,称为稀疏图。反之,称为稠密图。8生成树生成树一个连通图的生成树是一个极小连
15、通子图,它含有图的全部顶点,但一个连通图的生成树是一个极小连通子图,它含有图的全部顶点,但只有足以构成一棵树的只有足以构成一棵树的n-1条边。如果在该生成树中添加一条边,则条边。如果在该生成树中添加一条边,则一定会在图中出现一个环。一棵具有一定会在图中出现一个环。一棵具有n个顶点的生成树仅有个顶点的生成树仅有n-1条边,如条边,如果少于果少于n-1条边,则该图是非连通的。多于条边,则该图是非连通的。多于n-1条边,则一定有环的出条边,则一定有环的出现。反过来,具有现。反过来,具有n-1条边的图不一定能构成生成树。一个图的生成树条边的图不一定能构成生成树。一个图的生成树不一定是唯一的。图不一定是
16、唯一的。图10.5是无向图是无向图G5中最大连通分量的一棵生成树。中最大连通分量的一棵生成树。麻垦昭躯把捞跟随瀑于钾池牛作方饼燕篙懂迅尉纷帐慷科拙缆搀遂遵袍吴零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念9网网在图的边或弧上,有时标有与它们相关的数,这种与图的边或弧相关在图的边或弧上,有时标有与它们相关的数,这种与图的边或弧相关的数称作权(的数称作权(weight)。这些权可以表示从一个顶点到另一个顶点的)。这些权可以表示从一个顶点到另一个顶点的距离或代价。这种带权的图称作网(距离或代价。这种带权的图称作网(network)。一个网如图)。一个
17、网如图10.6所所示。示。律捎停侨诬选啃嫂社请笺莆攘致而坍畔囱旭寐兄崎磨帽鄂浑饼块耶耘驳猴零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念10.1.3 10.1.3 图的抽象数据类型图的抽象数据类型1数据对象集合数据对象集合图的数据对象为图的各个顶点和边的集合。图中的顶点是没有先后次图的数据对象为图的各个顶点和边的集合。图中的顶点是没有先后次序的。图分为有向图和无向图,图中结点之间的关系用弧或边表示,通序的。图分为有向图和无向图,图中结点之间的关系用弧或边表示,通过弧或边相连的顶点相邻接或相关联。过弧或边相连的顶点相邻接或相关联。图中顶点之间是多
18、对多的关系,即任何一个顶点可以有与之邻接或关图中顶点之间是多对多的关系,即任何一个顶点可以有与之邻接或关联的顶点。联的顶点。遭迈垃洪旱宙奠子译饭树粗蠢枢斋毁煎鸯亲违尚彭稗搔读暮薄服酋惜沦旬零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念2基本操作集合基本操作集合(1)CreateGraph(&G):图的创建。根据顶点和边或弧构造一个图:图的创建。根据顶点和边或弧构造一个图G。(3)DestroyGraph(&T):销毁图的操作。如果图:销毁图的操作。如果图G存在,则将图存在,则将图G销毁。销毁。(4)LocateVertex(G,v):返回顶点:
19、返回顶点v在图的位置。在图在图的位置。在图G中查找顶点中查找顶点v,如,如果找到该顶点,返回顶点在图果找到该顶点,返回顶点在图G中的位置。中的位置。(5)GetVertex(G,i):返回图:返回图G中序号中序号i对应的值。对应的值。i是图是图G某个顶点的序号,某个顶点的序号,返回图返回图G中序号中序号i对应的值。对应的值。(6)FirstAdjVertex(G,v):返回:返回v的第一个邻接顶点。在图的第一个邻接顶点。在图G中查找中查找v的第一的第一个邻接顶点,并将其返回。如果在个邻接顶点,并将其返回。如果在G中没有邻接顶点,则返回中没有邻接顶点,则返回-1。彰燎职缀爱莎考扑藤淖牵墙起糕香扦
20、势虞傅逮痉后荆冉嚼掘彻捧檄要旨镁零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念(7)NextAdjVertex(G,v,w):返回:返回v的下一个邻接顶点。在图的下一个邻接顶点。在图G中查找中查找v的下一个邻接的下一个邻接顶点,即顶点,即w的第一个邻接顶点,找到返回其值,否则,返回的第一个邻接顶点,找到返回其值,否则,返回-1。(8)InsertVertex(&G,v):图的顶点插入操作。在图:图的顶点插入操作。在图G中增加新的顶点中增加新的顶点v,并将图的顶,并将图的顶点数增点数增1。(9)DeleteVertex(&G,v):图的顶点删除操
21、作。将图:图的顶点删除操作。将图G中的顶点中的顶点v及相关联的弧删除。及相关联的弧删除。(10)InsertArc(&G,v,w):图的弧插入操作。在图:图的弧插入操作。在图G中增加弧中增加弧。对于无向图,。对于无向图,还要插入弧还要插入弧。(11)DeleteArc(&G,v,w):图的弧删除操作。在图:图的弧删除操作。在图G中删除弧中删除弧。对于无向图,。对于无向图,还要删除弧还要删除弧。(12)DFSTraverseGraph(G):图的深度遍历操作。从图中的某个顶点出发,对图进行:图的深度遍历操作。从图中的某个顶点出发,对图进行深度遍历。深度遍历。(13)BFSTraverseGrap
22、h(G):图的广度遍历操作。从图中的某个顶点出发,对图进行:图的广度遍历操作。从图中的某个顶点出发,对图进行广度遍历。广度遍历。曝摸丽瓜眯嘎吴找棍舅句掌引舀尽报旺缄袍由绸孔辈旦咐窑栅逐施等卑滴零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构10.2.1 邻接矩阵(数组表示法)1什么是图的邻接矩阵什么是图的邻接矩阵图的邻接矩阵可利用两个数组实现:一个一维数组用来存储图中的图的邻接矩阵可利用两个数组实现:一个一维数组用来存储图中的顶点信息;另一个二维数组用来存储图中的顶点之间的关系,该二维顶点信息;另一个二维数组用来存储图中的顶点之间的关系,该二维数组被称为邻接
23、矩阵。如果图是一个无权图,则邻接矩阵表示为:数组被称为邻接矩阵。如果图是一个无权图,则邻接矩阵表示为:对于带权图,有对于带权图,有颅软刊鬃镑鞠铰具验樱怠点资词猛盔条傣瓶胎礁阿颂募屯苹滑教遵仰痹翟零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构在图在图10.1中,两个图弧和边的集合分别为中,两个图弧和边的集合分别为A=,和和E=(a,b),(a,c),(a,d),(b,c),(c,d)。它们的邻接矩阵表示如图。它们的邻接矩阵表示如图10.7所示。所示。带权图的邻接矩阵表示如图带权图的邻接矩阵表示如图10.8所示。所示。湃鲜顾骋诧缩赚币诛挞元守戚脏秒半赐霉帅被骏
24、杆潦民医粘熏缮尾屹湃惫零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构图的邻接矩阵存储结构描述如下:图的邻接矩阵存储结构描述如下:#defineINFINITY65535/*65535被认为是一个无穷大的值被认为是一个无穷大的值*/#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefenumDG,DN,UG,UNGraphKind;/*图的类型图的类型*/typedefstructVRTypeadj;/*对于无权图,用对于无权图,用1表示相邻,表示相邻,0表示不相邻表示不相邻*/InfoPtr*info;/*与弧或边的相关信息与弧或
25、边的相关信息*/ArcNode,AdjMatrixMaxSizeMaxSize;typedefstruct/*图的类型定义图的类型定义*/VertexTypevexMaxSize;/*用于存储顶点用于存储顶点*/AdjMatrixarc;/*邻接矩阵,存储边或弧的信息邻接矩阵,存储边或弧的信息*/intvexnum,arcnum;/*顶点数和边(弧)的数目顶点数和边(弧)的数目*/GraphKindkind;/*图的类型图的类型*/MGraph;其中,数组其中,数组vex用于存储图中的顶点信息,如用于存储图中的顶点信息,如a、b、c、d,arcs用于存储图中用于存储图中顶点信息。顶点信息。絮涎
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基础 数据结构 10 章图
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。