零基础学数据结构第10章图.ppt

第第10章章图图图图(graph)是是一一种种比比线线性性表表、树树更更为为复复杂杂的的数数据据结结构构。在在线线性性表表中中，数数据据元元素素之之间间呈呈线线性性关关系系，即即每每个个元元素素只只有有一一个个直直接接前前驱驱和和一一个个直直接接后后继继。图图的的应应用用领领域域十十分分广广泛泛，如如化化学学分分析析、工工程程设设计计、遗遗传传学学、人人工工智智能能等等。本本章章主主要要介介绍绍图图的的定定义义、图图的的存存储储结结构构、图图的的遍遍历历、最小生成树、关键路径和最短路径。最小生成树、关键路径和最短路径。本章重点：本章重点：1 1、图的定义及性质、图的定义及性质 2 2、图的邻接矩阵和邻接表表示、图的邻接矩阵和邻接表表示 3 3、图的各种遍历、图的各种遍历 4 4、最小生成树、最小生成树 5 5、关键路径、关键路径 6 6、最短路径、最短路径辰枉储哎眼子皱蝴受灸龄蕉级蚁夸咆诫诗铁爸锣恫埠蠕寇妇联柯孜弱笛诗零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念图图G也是由数据元素集合也是由数据元素集合V与边的集合与边的集合E构成的。在图中，数据元构成的。在图中，数据元素通常称为顶点（素通常称为顶点（Vertex）。其中，顶点集合）。其中，顶点集合V不能为空，边表示不能为空，边表示顶点之间的关系。顶点之间的关系。若若E，则，则表示从顶点表示从顶点x到顶点到顶点y存在一条弧存在一条弧（Arc），），x称为弧尾（称为弧尾（tail）或起始点（）或起始点（initialnode），），y称为弧称为弧头（头（head）或终端点（）或终端点（terminalnode）。这样的图被称为有向图）。这样的图被称为有向图（digraph）。）。如果如果E且有且有E，即，即E是对称的，则用无序对是对称的，则用无序对(x,y)代替有序对代替有序对和和，表示，表示x与与y之间存在一条边之间存在一条边（edge），这样的图称为无向图（），这样的图称为无向图（undigraph）。如图）。如图10.1所示。所示。称副舶恒呻早飘钉券磋玫斗兰党将历唉崔鄙傻垦塑粉酗截箕旷锐裹伍抱垦零基础学数据结构第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=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)，若弧，若弧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和和c相关联。相关联。抬衣猴影磨垫乍褥糟躲鞘次每泻糊题丘嗡宵俩铂拱您袄案悠戊不置淫佰砸零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念2顶点的度顶点的度对于无向图，顶点对于无向图，顶点v的度是指与的度是指与v相关联的边的数目，记作相关联的边的数目，记作TD(v)。对于。对于有向图，以顶点有向图，以顶点v为弧头的数目称为顶点为弧头的数目称为顶点v的入度的入度(indegree)，记作，记作ID(v)。以顶点。以顶点v为弧尾的数目称为为弧尾的数目称为v的出度的出度(outdegree)，记作，记作OD(v)。顶点。顶点v的度的度(degree)为为TD(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=绞氮籍傍骇商根籽嘉孩辰贞衔蒙聪乘搞学婿彬果滇敦并烤纫爵沥穆碱首虚零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念3路径路径无向图无向图G中，从顶点中，从顶点v到顶点到顶点v的路径（的路径（path）是从）是从v出发，经出发，经过一系列的顶点序列到达顶点过一系列的顶点序列到达顶点v。如果。如果G是有向图，则路径也是有向是有向图，则路径也是有向的，路径的长度是路径上弧或边的数目。第一个顶点和最后一个顶的，路径的长度是路径上弧或边的数目。第一个顶点和最后一个顶点相同的路径称为回路或环（点相同的路径称为回路或环（cycle）。序列中顶点不重复出现的路）。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外，其他顶点不径称为简单路径。除了第一个顶点和最后一个顶点外，其他顶点不重复出现的回路，称为简单回路或简单环。重复出现的回路，称为简单回路或简单环。在图在图10.1所示的有向图所示的有向图G1中，顶点序列中，顶点序列adca构成了一构成了一个简单回路。在无向图个简单回路。在无向图G2中，从顶点中，从顶点a到顶点到顶点c所经过的路径为所经过的路径为a，d和和c（或（或a、b、c）。）。妆瓜戴腿屡维陡瘸劳膘以晨弘剖谴皋赌塔街蕴拼颤淳腋瞳啦拧邮橱箍窘泄零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念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和和vj都是连通的，则称都是连通的，则称G是连通图（是连通图（connectedgraph）。无向图中的极大连通子图称为连通）。无向图中的极大连通子图称为连通分量。无向图分量。无向图G3与连通分量如图与连通分量如图10.3所示。所示。蔓秽即瑞茸沟蜡扛货台乏师捷坝文款驰渺栈诵试粒掣宛力邦颓星坏睫阀撤零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念对于有向图对于有向图G，如果对每一对顶点，如果对每一对顶点vi和和vj，且，且vivj，从，从vi到到vj和和vj到到vi都存在路径，则都存在路径，则G为强连通图。有向图中的极大强连通子图称为为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。有向图有向图的强连通分量。有向图G4与强连通分量如图与强连通分量如图10.4所示。所示。啡惦首肌赋累奢蜘园淬局赤楔腻眨钾虏燕代否微纫妆限焊韦帜于继自仓膊零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念6完全图完全图若图的顶点数目是若图的顶点数目是n，图的边（弧）的数目是，图的边（弧）的数目是e。若不存在顶点到。若不存在顶点到自身的边或弧，即若存在自身的边或弧，即若存在，则有，则有vivj。对于无向图，边数。对于无向图，边数e的取值范围为的取值范围为0n(n-1)/2。将具有。将具有n(n-1)/2条边的无向图称为完全条边的无向图称为完全图（图（completedgraph）或无向完全图。对于有向图，弧数）或无向完全图。对于有向图，弧数e的取值的取值范围是范围是0n(n-1)。将具有。将具有n(n-1)条弧的有向图称为有向完全图。条弧的有向图称为有向完全图。宇妒匣柱赘掷种僳捡免汉嫂欢具字喜稚砂崩饮豁册涝疏温怀趁在乏嫡战帜零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念7稀疏图和稠密图稀疏图和稠密图具有具有enlogn条弧或边的图，称为稀疏图。反之，称为稠密图。条弧或边的图，称为稀疏图。反之，称为稠密图。8生成树生成树一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但只有足以构成一棵树的只有足以构成一棵树的n-1条边。如果在该生成树中添加一条边，则条边。如果在该生成树中添加一条边，则一定会在图中出现一个环。一棵具有一定会在图中出现一个环。一棵具有n个顶点的生成树仅有个顶点的生成树仅有n-1条边，如条边，如果少于果少于n-1条边，则该图是非连通的。多于条边，则该图是非连通的。多于n-1条边，则一定有环的出条边，则一定有环的出现。反过来，具有现。反过来，具有n-1条边的图不一定能构成生成树。一个图的生成树条边的图不一定能构成生成树。一个图的生成树不一定是唯一的。图不一定是唯一的。图10.5是无向图是无向图G5中最大连通分量的一棵生成树。中最大连通分量的一棵生成树。麻垦昭躯把捞跟随瀑于钾池牛作方饼燕篙懂迅尉纷帐慷科拙缆搀遂遵袍吴零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念9网网在图的边或弧上，有时标有与它们相关的数，这种与图的边或弧相关在图的边或弧上，有时标有与它们相关的数，这种与图的边或弧相关的数称作权（的数称作权（weight）。这些权可以表示从一个顶点到另一个顶点的）。这些权可以表示从一个顶点到另一个顶点的距离或代价。这种带权的图称作网（距离或代价。这种带权的图称作网（network）。一个网如图）。一个网如图10.6所所示。示。律捎停侨诬选啃嫂社请笺莆攘致而坍畔囱旭寐兄崎磨帽鄂浑饼块耶耘驳猴零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念10.1.3 10.1.3 图的抽象数据类型图的抽象数据类型1数据对象集合数据对象集合图的数据对象为图的各个顶点和边的集合。图中的顶点是没有先后次图的数据对象为图的各个顶点和边的集合。图中的顶点是没有先后次序的。图分为有向图和无向图，图中结点之间的关系用弧或边表示，通序的。图分为有向图和无向图，图中结点之间的关系用弧或边表示，通过弧或边相连的顶点相邻接或相关联。过弧或边相连的顶点相邻接或相关联。图中顶点之间是多对多的关系，即任何一个顶点可以有与之邻接或关图中顶点之间是多对多的关系，即任何一个顶点可以有与之邻接或关联的顶点。联的顶点。遭迈垃洪旱宙奠子译饭树粗蠢枢斋毁煎鸯亲违尚彭稗搔读暮薄服酋惜沦旬零基础学数据结构第10章图零基础学数据结构第10章图10.1图的定义与相关概念图的定义与相关概念2基本操作集合基本操作集合（1）CreateGraph(&G)：图的创建。根据顶点和边或弧构造一个图：图的创建。根据顶点和边或弧构造一个图G。（3）DestroyGraph(&T)：销毁图的操作。如果图：销毁图的操作。如果图G存在，则将图存在，则将图G销毁。销毁。（4）LocateVertex(G,v)：返回顶点：返回顶点v在图的位置。在图在图的位置。在图G中查找顶点中查找顶点v，如，如果找到该顶点，返回顶点在图果找到该顶点，返回顶点在图G中的位置。中的位置。（5）GetVertex(G,i)：返回图：返回图G中序号中序号i对应的值。对应的值。i是图是图G某个顶点的序号，某个顶点的序号，返回图返回图G中序号中序号i对应的值。对应的值。（6）FirstAdjVertex(G,v)：返回：返回v的第一个邻接顶点。在图的第一个邻接顶点。在图G中查找中查找v的第一的第一个邻接顶点，并将其返回。如果在个邻接顶点，并将其返回。如果在G中没有邻接顶点，则返回中没有邻接顶点，则返回-1。彰燎职缀爱莎考扑藤淖牵墙起糕香扦势虞傅逮痉后荆冉嚼掘彻捧檄要旨镁零基础学数据结构第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)：图的顶点删除操作。将图：图的顶点删除操作。将图G中的顶点中的顶点v及相关联的弧删除。及相关联的弧删除。（10）InsertArc(&G,v,w)：图的弧插入操作。在图：图的弧插入操作。在图G中增加弧中增加弧。对于无向图，。对于无向图，还要插入弧还要插入弧。（11）DeleteArc(&G,v,w)：图的弧删除操作。在图：图的弧删除操作。在图G中删除弧中删除弧。对于无向图，。对于无向图，还要删除弧还要删除弧。（12）DFSTraverseGraph(G)：图的深度遍历操作。从图中的某个顶点出发，对图进行：图的深度遍历操作。从图中的某个顶点出发，对图进行深度遍历。深度遍历。（13）BFSTraverseGraph(G)：图的广度遍历操作。从图中的某个顶点出发，对图进行：图的广度遍历操作。从图中的某个顶点出发，对图进行广度遍历。广度遍历。曝摸丽瓜眯嘎吴找棍舅句掌引舀尽报旺缄袍由绸孔辈旦咐窑栅逐施等卑滴零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构10.2.1 邻接矩阵（数组表示法）1什么是图的邻接矩阵什么是图的邻接矩阵图的邻接矩阵可利用两个数组实现：一个一维数组用来存储图中的图的邻接矩阵可利用两个数组实现：一个一维数组用来存储图中的顶点信息；另一个二维数组用来存储图中的顶点之间的关系，该二维顶点信息；另一个二维数组用来存储图中的顶点之间的关系，该二维数组被称为邻接矩阵。如果图是一个无权图，则邻接矩阵表示为：数组被称为邻接矩阵。如果图是一个无权图，则邻接矩阵表示为：对于带权图，有对于带权图，有颅软刊鬃镑鞠铰具验樱怠点资词猛盔条傣瓶胎礁阿颂募屯苹滑教遵仰痹翟零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构在图在图10.1中，两个图弧和边的集合分别为中，两个图弧和边的集合分别为A=,和和E=(a,b),(a,c),(a,d),(b,c),(c,d)。它们的邻接矩阵表示如图。它们的邻接矩阵表示如图10.7所示。所示。带权图的邻接矩阵表示如图带权图的邻接矩阵表示如图10.8所示。所示。湃鲜顾骋诧缩赚币诛挞元守戚脏秒半赐霉帅被骏杆潦民医粘熏缮尾屹湃惫零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构图的邻接矩阵存储结构描述如下：图的邻接矩阵存储结构描述如下：#defineINFINITY65535/*65535被认为是一个无穷大的值被认为是一个无穷大的值*/#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefenumDG,DN,UG,UNGraphKind;/*图的类型图的类型*/typedefstructVRTypeadj;/*对于无权图，用对于无权图，用1表示相邻，表示相邻，0表示不相邻表示不相邻*/InfoPtr*info;/*与弧或边的相关信息与弧或边的相关信息*/ArcNode,AdjMatrixMaxSizeMaxSize;typedefstruct/*图的类型定义图的类型定义*/VertexTypevexMaxSize;/*用于存储顶点用于存储顶点*/AdjMatrixarc;/*邻接矩阵，存储边或弧的信息邻接矩阵，存储边或弧的信息*/intvexnum,arcnum;/*顶点数和边（弧）的数目顶点数和边（弧）的数目*/GraphKindkind;/*图的类型图的类型*/MGraph;其中，数组其中，数组vex用于存储图中的顶点信息，如用于存储图中的顶点信息，如a、b、c、d，arcs用于存储图中用于存储图中顶点信息。顶点信息。絮涎书音先神映董锭谐翼政靴梦甘晰胞稍牲俯力廊秒胖辨撂瑞俐针速幻肆零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构2邻接矩阵应用举例邻接矩阵应用举例【例【例10_1】试编写一个算法，采用邻接矩阵创建一个如图】试编写一个算法，采用邻接矩阵创建一个如图10.8所所示的有向网示的有向网G。分析：主要考察图的邻接矩阵表示与算法实现。图的创建包括两分析：主要考察图的邻接矩阵表示与算法实现。图的创建包括两个部分：一个是创建顶点，顶点信息可存储到一个向量（一维数组）个部分：一个是创建顶点，顶点信息可存储到一个向量（一维数组）中；一个是创建弧的信息，包括弧的相关顶点和权值，可存储到二中；一个是创建弧的信息，包括弧的相关顶点和权值，可存储到二维数组中，其中，二维数组的两个下标分别表示两个相关顶点在矩维数组中，其中，二维数组的两个下标分别表示两个相关顶点在矩阵中的行号和列号，权值存入到数组中。阵中的行号和列号，权值存入到数组中。囤乒炭广甸咨扒箭骋赔舞泣瓮渺蹿愤沙失族馈芋绣封衫御焕氯雌必母咽怯零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构10.2.2 邻接表邻接表（邻接表（adjacencylist）是图的一种链式存储方式。采用邻接表）是图的一种链式存储方式。采用邻接表表示图一般需要两个表结构：边表和表头结点表。表示图一般需要两个表结构：边表和表头结点表。边表：在邻接表中，对图中的每个顶点都建立一个单链表，第边表：在邻接表中，对图中的每个顶点都建立一个单链表，第i个个单链表中的结点表示依附于顶点单链表中的结点表示依附于顶点vi的边（对有向图来说是以顶点的边（对有向图来说是以顶点vi为为尾的弧），这种链表称为边表，其中结点称为弧结点，弧结点由尾的弧），这种链表称为边表，其中结点称为弧结点，弧结点由3个个域组成：邻接点域（域组成：邻接点域（adjvex）、数据域（）、数据域（info）和指针域）和指针域（nextarc）。其中，邻接点域表示与相应的表头顶点邻接点的位置，）。其中，邻接点域表示与相应的表头顶点邻接点的位置，数据域存储与边或弧的信息，指针域用来指示下一个边或弧的结点。数据域存储与边或弧的信息，指针域用来指示下一个边或弧的结点。枢痒期贸毅碗酪膜啮绿敖奖跑邱毁楔晶戊舟叭悍泅弛巧晦茨远矫竭盔佰怨零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构表头结点表：在每个链表前面设置一个头结点，除了设有存储各表头结点表：在每个链表前面设置一个头结点，除了设有存储各个顶点信息的数据域（个顶点信息的数据域（data）外，还设有指向链表中第一个结点的）外，还设有指向链表中第一个结点的链域（链域（firstarc），我们把这种表称为表头结点表，相应地，结点称），我们把这种表称为表头结点表，相应地，结点称为表头结点。通常情况下，表头结点采用顺序存储结构实现，这样为表头结点。通常情况下，表头结点采用顺序存储结构实现，这样可以随机地访问任意顶点。可以随机地访问任意顶点。边表结点和表头结点的结构如图边表结点和表头结点的结构如图10.10所示。所示。望肝囊漾贵算讹聘委休俯羹努黍崖苔吊炊哎挨淑稠酥碑疆躯帽递痛张引呆零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构图图10.1所示的图所示的图G1和和G2用邻接表表示如图用邻接表表示如图10.11所示。所示。图图10.8所示的带权图的邻接表如图所示的带权图的邻接表如图10.12所示。所示。赃晾毋丑预烽躺厨卑欺蒙翻推禄龚儡伎吧犯首贫买敝术撬羽布瓮眉让闺深零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构图的邻接表存储结构描述如下：图的邻接表存储结构描述如下：#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefenumDG,DN,UG,UNGraphKind;/*图的类型：有向图、有向图的类型：有向图、有向网、无向图和无向网网、无向图和无向网*/typedefstructArcNode/*边结点的类型定义边结点的类型定义*/intadjvex;/*弧指向的顶点的位置弧指向的顶点的位置*/InfoPtr*info;/*与弧相关的信息与弧相关的信息*/structArcNode*nextarc;/*指示下一个与该顶点相邻接的顶点指示下一个与该顶点相邻接的顶点*/ArcNode;typedefstructVNode/*头结点的类型定义头结点的类型定义*/VertexTypedata;/*用于存储顶点用于存储顶点*/ArcNode*firstarc;/*指示第一个与该顶点邻接的顶点指示第一个与该顶点邻接的顶点*/VNode,AdjListMaxSize;烧聊赁碗宁埠纸嘲驼屉氛牵埔蒸杉疥禽刮椿馒泰溅瓜挪甘舍筹扫秩婿恬档零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构typedefstruct/*图的类型定义图的类型定义*/AdjListvertex;intvexnum,arcnum;/*图的顶点数目与弧的数目图的顶点数目与弧的数目*/GraphKindkind;/*图的类型图的类型*/AdjGraph;如果无向图如果无向图G中有中有n个顶点和个顶点和e条边，则图采用邻接表表示，需要条边，则图采用邻接表表示，需要n个头结点和个头结点和2e个表结点。在个表结点。在e远小于远小于n(n-1)/2时，采用邻接表存储表时，采用邻接表存储表示显然要比采用邻接矩阵表示更能节省空间。示显然要比采用邻接矩阵表示更能节省空间。屎司糙蔡抽倡秆夕卒舜兽绥隘拟抡格宅利械簇勘强鸵宜社扎儿啤区祸绰仔零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构有有时时为为了了便便于于求求某某个个顶顶点点的的入入度度，需需要要建建立立一一个个有有向向图图的的逆逆邻邻接接链链表表，也也就就是是为为每每个个顶顶点点vi建建立立一一个个以以vi为为弧弧头头的的链链表表。在在邻邻接接表表中中，边边表表结结点点的的邻邻接接点点域域的的值值为为i的的个个数数，就就是是顶顶点点vi的的入入度度。因因此此如如果果要要求求某某个个顶顶点点的的入入度度，则则需需要要对对整整个个邻邻接接表表进进行行遍遍历历。图图10.1所示的有向图所示的有向图G1的逆邻接链表如图的逆邻接链表如图10.13所示。所示。欧订搭龟瑟形猜拔互层晒塔婆矿猿茫鼎涎鹃届沫姬揣斩枕圈换踊瓢佩撩沂零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构【例【例10_2】编写一个创建如图】编写一个创建如图10.1所示的无向图（假设采用邻接表表示图所示的无向图（假设采用邻接表表示图）。）。分析：主要考察图的邻接表存储结构。图的创建包括两个部分：创建表头分析：主要考察图的邻接表存储结构。图的创建包括两个部分：创建表头结点和边表结点。其中，表头结点利用一个数组实现，数组包括两个域：一结点和边表结点。其中，表头结点利用一个数组实现，数组包括两个域：一个保存顶点的值；一个是指针，用于指向与顶点相关联的顶点对应结点。代个保存顶点的值；一个是指针，用于指向与顶点相关联的顶点对应结点。代码如下：码如下：for(i=0;ivexnum;i+)/*将顶点存储在表头结点中将顶点存储在表头结点中*/scanf(%s,G-vertexi.data);G-vertexi.firstarc=NULL;/*将相关联的顶点置为空将相关联的顶点置为空*/入肌窍笛毯秆众游怜肢巧汪缎植冠井候驴矽墒霜舰趁鉴互换黎也鄙穴霹华零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构10.2.3 十字链表十字链表（十字链表（orthogonallist）是有向图的另一种链式存储结构，）是有向图的另一种链式存储结构，它可以看作是将有向图的邻接表与逆邻接链表结合起来的得到的一它可以看作是将有向图的邻接表与逆邻接链表结合起来的得到的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也有一个结点，这些结点的结构如图应于每个顶点也有一个结点，这些结点的结构如图10.15所示。所示。弧结点包含弧结点包含5个域：尾域个域：尾域tailvex、头域、头域headvex、infor域和两个域和两个指针域指针域hlink、tlink。其中，尾域。其中，尾域tailvex用于表示弧尾顶点在图中用于表示弧尾顶点在图中的位置，头域的位置，头域headvex表示弧头顶点在图中的位置，表示弧头顶点在图中的位置，info域表示弧域表示弧的相关信息，指针域的相关信息，指针域hlink指向弧头相同的下一个条弧，指向弧头相同的下一个条弧，tlink指向弧指向弧尾相同的下一条弧。尾相同的下一条弧。鸳憨墩托男劳冲须罚猿建绦坠豪持枣讯储炊襄奸析狡晨去孕报物芥丑黄砾零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构顶点结点包含顶点结点包含3个域：个域：data域和域和firstin、firstout域，其中，域，其中，data域域存储与顶点相关的信息，如顶点的名称，存储与顶点相关的信息，如顶点的名称，firstin和和firstout是两个指针是两个指针域，分别指向以该顶点为弧头和弧尾的第一个弧度结点。域，分别指向以该顶点为弧头和弧尾的第一个弧度结点。有向图有向图G1的十字链表存储表示如图的十字链表存储表示如图10.16所示。所示。轻神入所贡诱碱焚氟胎是嚏禄四吊瘤绢嫁味田菌候反难葡死嗣徊尊苛唇辛零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构有向图的十字链表存储结构描述如下：有向图的十字链表存储结构描述如下：#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefstructArcNode/*弧结点的类型定义弧结点的类型定义*/intheadvex,tailvex;/*弧的头顶点和尾顶点位置弧的头顶点和尾顶点位置*/InfoPtr*info;/*与弧相关的信息与弧相关的信息*/struct*hlink,*tlink;/*指示弧头和弧尾相同的结点指示弧头和弧尾相同的结点*/ArcNode;typedefstructVNode/*顶点结点的类型定义顶点结点的类型定义*/VertexTypedata;/*用于存储顶点用于存储顶点*/ArcNode*firstin,*firstout;/*分别指向顶点的第一条入弧和出弧分别指向顶点的第一条入弧和出弧*/VNode;typedefstruct/*图的类型定义图的类型定义*/VNodevertexMaxSize;intvexnum,arcnum;/*图的顶点数目与弧的数目图的顶点数目与弧的数目*/OLGraph;强徐胃捉匆恤震夕旬园拣傅哺扒罕端缓雕绎禽贮锅确麓鲜棱派哥蹿拖棺缠零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构10.2.4 10.2.4 邻接多重链表邻接多重链表邻接多重链表（邻接多重链表（adjacencymultilist）是无向图的另一种链式）是无向图的另一种链式存储结构。在无向图的邻接表存储表示中，虽然很容易求得顶点和存储结构。在无向图的邻接表存储表示中，虽然很容易求得顶点和边的各种信息，但是对于每一条边（边的各种信息，但是对于每一条边（vi，vj）都有两个结点，分别在）都有两个结点，分别在第第i个和第个和第j个链表中，这给图的某些操作带来不变，例如，要删除一个链表中，这给图的某些操作带来不变，例如，要删除一条边，此时需要找到表示同一条边的两个顶点。因此，在进行这一条边，此时需要找到表示同一条边的两个顶点。因此，在进行这一类操作时，采用邻接多重链表比较合适，邻接多重链表是将图的一类操作时，采用邻接多重链表比较合适，邻接多重链表是将图的一条边用一个结点表示。它的结点结构如图条边用一个结点表示。它的结点结构如图10.17所示。所示。韭揉跳俘乒噶燃蕊许阮吞择材喂川滥约乒砷抿股岛蛤淀棒饲侄孵羚攘辐游零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构无向图无向图G2的多重链表如图的多重链表如图10.18所示。所示。杨量土福界蔷杰刹郭旱俊泪催畜懂丝戚疗另侈诉车黍旗慈撤蔬达梨抚爬冶零基础学数据结构第10章图零基础学数据结构第10章图10.2图的存储结构图的存储结构无向图的多重链表存储结构描述如下：无向图的多重链表存储结构描述如下：#defineMaxSize50/*最大顶点个数最大顶点个数*/typedefstructEdgeNode/*边结点的类型定义边结点的类型定义*/intmark,ivex,jvex;/*访问标志和边的两个顶点位置访问标志和边的两个顶点位置*/InfoPtr*info;/*与边相关的信息与边相关的信息*/struct*ilink,*jlink;/*指示与边顶点相同的结点指示与边顶点相同的结点*/EdgeNode;typedefstructVNode/*顶点结点的类型定义顶点结点的类型定义*/VertexTypedata;/*用于存储顶点用于存储顶点*/EdgeNode*firstedge;/*指向依附于顶点的第一条边指向依附于顶点的第一条边*/VexNode;typedefstruct/*图的类型定义图的类型定义*/VexNodevertexMaxSize;intvexnum,edgenum;/*图的顶点数目与边的数目图的顶点数目与边的数目*/AdjMultiGraph;补吴付蜕屹配粘狈场捂彼属刨走龋戳霄镀打若肃喀的源厅忠黔第闰顿攻杨零基础学数据结构第10章图零基础学数据结构第10章图10.3图的遍历图的遍历与树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶与树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做图的遍历点，且使每一个顶点仅被访问一次。这一过程就叫做图的遍历（traversinggraph）。）。10.3.1 图的深度优先搜索1什么是图的深度搜索什么是图的深度搜索图的深度优先搜索（图的深度优先搜索（depth_firstsearch）遍历类似于树的先）遍历类似于树的先根遍历，是树的先根遍历的推广。图的深度优先遍历的思想是：假根遍历，是树的先根遍历的推广。图的深度优先遍历的思想是：假设初始状态是图中所有顶点未曾被访问，从图中某个顶点设初始状态是图中所有顶点未曾被访问，从图中某个顶点v0出发，出发，访问顶点访问顶点v0。然后依次从。然后依次从v0的未被访问的邻接点出发深度优先遍历的未被访问的邻接点出发深度优先遍历图，直至图中所有和图，直至图中所有和v0有路径相通的顶点都被访问到；若此时图中有路径相通的顶点都被访问到；若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复执行上述过程，直到图中所有的顶点都被访问过。重复执行上述过程，直到图中所有的顶点都被访问过。贸寓避刀莉材藏委岁踪操梧显戏獭邵颜区卖锭焰翠茬泞础蕴渤象粮刮阳那零基础学数据结构第10章图零基础学数据结构第10章图10.3图的遍历图的遍历图图的的深深度度优优先先搜搜索索遍遍历历过过程程如如图图10.18所所示示。实实箭箭头头表表示示访访问问顶顶点的方向，虚箭头表示回溯，数字表示访问或回溯的次序。点的方向，虚箭头表示回溯，数字表示访问或回溯的次序。甘判邦隧洒暇盲龋瓣点潮戚镶么舍郭搞能袱昂缉耶刻科傻忙雾激音探轿恩零基础学数据结构第10章图零基础学数据结构第10章图10.3图的遍历图的遍历2图的深度优先搜索遍历的算法实现图的深度优先搜索遍历的算法实现图的深度优先遍历（邻接表实现）的算法描述如下。图的深度优先遍历（邻接表实现）的算法描述如下。intvisitedMaxSize;/*访问标志数组访问标志数组*/voidDFSTraverse(AdjGraphG)/*从第从第1个顶点起，深度优先搜索遍历图个顶点起，深度优先搜索遍历图G*/intv;for(v=0;vG.vexnum;v+)visitedv=0;/*访问标志数组初始化为未被访问访问标志数组初始化为未被访问*/for(v=0;v=0;w=NextAdjVertex(G,G.vertexv.data,G.vertexw.data)if(!visitedw)DFS(G,w);/*递归调用递归调用DFS对对v的尚未访的尚未访问的序号为问的序号为w的邻接顶点的邻接顶点*/宰衬肘轴刽扳泳砖徒迢虽圆郭舆龟蛮掖逐估螟辆祝挞闪袒仅捂砍属怠屑了零基础学数据结构第10章图零基础学数据结构第10章图10.3图的遍历图的遍历如如果果该该图图是是一一个个无无向向连连通通图图或或者者该该图图是是一一个个强强连连通通图图，则则只只需需要要调调 用用 一一 次次 DFS(G,v)就就 可可 以以 遍遍 历历 整整 个个 图图，否否 则则 需需 要要 多多 次次 调调 用用DFS(G,v)。在在 遍遍 历历 图图 时时，对对 图图 中中 的的 每每 个个 顶顶 点点 至至 多多 调调 用用 一一 次次DFS(G,v)函函数数，因因为为一一旦旦某某个个顶顶点点被被标标志志为为已已被被访访问问，就就不不再再从从它它出出发发进进行行搜搜索索。因因此此，遍遍历历图图的的过过程程实实质质上上是是对对每每个个顶顶点点查查找找其其邻邻接接点点的的过过程程。其其时时间间耗耗费费取取决决于于所所采采用用的的存存储储结结构构。当当用用二二维维数数组组表表示示邻邻接接矩矩阵阵作作为为图图的的存存储储结结构构时时，查查找找每每个个顶顶点点的的邻邻接接点点所所需需时时间间为为O(n2)，其其中中n为为图图中中的的顶顶点点数数。当当以以邻邻接接表表作作为为图图的的存存储储结结构构时时，查查找找邻邻接接点点的的时时间