数据结构第6章图.pptx
2023/2/14掌握图的定义及其基本术语；理解图的抽象数据类型定义；掌握图的邻接矩阵和邻接表存储；掌握图的遍历方法及其在邻接矩阵和邻接表存储结构上的实现；理解图的十字链表、邻接多重表和边集数组存储方法；理解无向图的连通性；了解有向图的连通性；掌握Prim算法和Kruskal算法的基本思想和求解过程；理解Prim算法和Kruskal算法的C+描述；掌握Dijkstra算法和Floyd算法的基本思想及求解过程；理解Dijkstra算法和Floyd算法的C+描述；掌握拓扑序列的定义及拓扑排序算法；掌握关键路径的定义及求解过程；理解求关键路径算法。图是一种非常复杂的非线性结构，并且具有极强的表达能力，现实世界中的许多问题都可以抽象为图结构。本章是本课程的难点和重点。通过本章的学习，要求学生：第第6 6章章 图图第1页/共169页欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。图论欧拉第2页/共169页能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？哥尼斯堡七桥问题第3页/共169页CADB七桥问题的图模型哥尼斯堡七桥问题欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。第4页/共169页图的定义图的定义6.16.1图的逻辑结构图的逻辑结构图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。第5页/共169页6.16.1图的逻辑结构图的逻辑结构如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为。如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。V1V2V3V4V5V1V2V3V4第6页/共169页6.16.1图的逻辑结构图的逻辑结构图的基本术语简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图 非简单图 简单图V1V2V3V4V5v 数据结构中讨论的都是简单图。第7页/共169页6.16.1图的逻辑结构图的逻辑结构图的基本术语邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。V1V2V3V4V5V1的邻接点：V2、V4V2的邻接点：V1、V3、V5第8页/共169页6.16.1图的逻辑结构图的逻辑结构图的基本术语邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧依附于顶点vi和顶点vj。V1V2V3V4V1的邻接点：V2、V3V3的邻接点：V4第9页/共169页在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比第10页/共169页在线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比第11页/共169页无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。图的基本术语V1V2V3V1V2V3V46.16.1图的逻辑结构图的逻辑结构第12页/共169页含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？6.16.1图的逻辑结构图的逻辑结构含有n个顶点的无向完全图有n(n-1)/2条边。含有n个顶点的有向完全图有n(n-1)条边。V1V2V3V1V2V3V4第13页/共169页稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。6.16.1图的逻辑结构图的逻辑结构图的基本术语顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。第14页/共169页V1V2V3V4V56.16.1图的逻辑结构图的逻辑结构图的基本术语在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？=niievTD12)(第15页/共169页V1V2V3V46.16.1图的逻辑结构图的逻辑结构图的基本术语在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？evODvIDiiii=11)()(nn第16页/共169页权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。6.16.1图的逻辑结构图的逻辑结构图的基本术语V1V2V3V42785第17页/共169页路径：在无向图G=(V,E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,vim=vq)，其中，(vij-1,vij)E（1jm）。若G是有向图，则路径也是有方向的，顶点序列满足E。6.16.1图的逻辑结构图的逻辑结构图的基本术语V1V2V3V4V5v一般情况下，图中的路径不惟一。V1到V4的路径：V1V4V1V2V3V4 V1V2V5V3V4第18页/共169页路径长度：6.16.1图的逻辑结构图的逻辑结构图的基本术语非带权图路径上边的个数带权图路径上各边的权之和V1V2V3V4V5V1V4：长度为1V1V2V3V4：长度为3V1V2V5V3V4：长度为4第19页/共169页路径长度：6.16.1图的逻辑结构图的逻辑结构图的基本术语非带权图路径上边的个数带权图路径上各边的权之和V1V4：长度为8V1V2V3V4：长度为7V1V2V5V3V4：长度为15V1V2V3V4V5256328第20页/共169页回路（环）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。6.16.1图的逻辑结构图的逻辑结构图的基本术语V1V2V3V4V5V1V2V3V4第21页/共169页子图：若图G=（V，E），G=（V，E），如果VV且EE，则称图G是G的子图。6.16.1图的逻辑结构图的逻辑结构图的基本术语V1V2V3V4V5V1V2V3V4V5V1V3V4第22页/共169页连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图的极大连通子图称为连通分量。6.16.1图的逻辑结构图的逻辑结构图的基本术语如何求得一个非连通图的连通分量?1.含有极大顶点数；2.依附于这些顶点的所有边。第23页/共169页连通分量16.16.1图的逻辑结构图的逻辑结构V1V2V3V4V5V6V7V1V2V4V5V3V6V7连通分量2图的基本术语v连通分量是对无向图的一种划分。第24页/共169页强连通图：在有向图中，对图中任意一对顶点vi和vj(ij)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。6.16.1图的逻辑结构图的逻辑结构图的基本术语如何求得一个非连通图的连通分量?第25页/共169页6.16.1图的逻辑结构图的逻辑结构图的基本术语V1V2V3V4强连通分量1强连通分量2V1V3V4V2第26页/共169页生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。如何理解极小连通子图?6.16.1图的逻辑结构图的逻辑结构图的基本术语多构成回路少不连通含有n-1条边第27页/共169页V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成森林6.16.1图的逻辑结构图的逻辑结构第28页/共169页图的抽象数据类型定义图的抽象数据类型定义 ADTGraphData顶点的有穷非空集合和边的集合OperationInitGraph前置条件：图不存在输入：无功能：图的初始化输出：无后置条件：构造一个空的图6.16.1图的逻辑结构图的逻辑结构第29页/共169页DFSTraverse前置条件：图已存在输入：遍历的起始顶点v功能：从顶点v出发深度优先遍历图输出：图中顶点的一个线性排列后置条件：图保持不变BFSTraverse前置条件：图已存在输入：遍历的起始顶点v功能：从顶点v出发广度优先遍历图输出：图中顶点的一个线性排列后置条件：图保持不变6.16.1图的逻辑结构图的逻辑结构第30页/共169页DestroyGraph前置条件：图已存在输入：无功能：销毁图输出：无后置条件：释放图所占用的存储空间GetVex前置条件：图已存在输入：顶点v功能：在图中查找顶点v的数据信息输出：顶点v的数据信息后置条件：图保持不变endADT6.16.1图的逻辑结构图的逻辑结构第31页/共169页图的遍历操作图的遍历操作图的遍历是在从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。6.16.1图的逻辑结构图的逻辑结构抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。第32页/共169页图的遍历操作要解决的关键问题在图中，如何选取遍历的起始顶点？6.16.1图的逻辑结构图的逻辑结构n在线性表中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的；n在树中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；n在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。解决方案：从编号小的顶点开始。第33页/共169页从某个起点始可能到达不了所有其它顶点，怎么办？6.16.1图的逻辑结构图的逻辑结构图的遍历操作要解决的关键问题解决方案：多次调用从某顶点出发遍历图的算法。v下面仅讨论从某顶点出发遍历图的算法。第34页/共169页因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环。在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？6.16.1图的逻辑结构图的逻辑结构图的遍历操作要解决的关键问题解决方案：附设访问标志数组visitedn。解决方案：深度优先遍历和广度优先遍历。第35页/共169页约翰霍普克洛夫特1939年生于西雅图。1961年进入斯坦福大学研究生院深造，1962年获硕士学位，1964年获博士学位。毕业后先后在普林斯顿大学、斯坦福大学等著名学府工作，也曾任职于一些科学研究机构如 NSF（美国科学基金会）和 NRC（美国国家研究院）。罗伯特陶尔扬1948年4月30日生于加利福尼亚州。1969年本科毕业，进入斯坦福大学研究生院，1972年获得博士学位。1986年图灵奖获得者6.16.1图的逻辑结构图的逻辑结构第36页/共169页1.深度优先遍历（类似于树的前序遍历）基本思想：访问顶点v；从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。6.16.1图的逻辑结构图的逻辑结构第37页/共169页深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8V1遍历序列：V1V2V2V4V4V5V5第38页/共169页深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8V1遍历序列：V1V2V2V4V4V5V8V8第39页/共169页深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8V1遍历序列：V1V2V2V4V4V5V8第40页/共169页深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8V1遍历序列：V1V7V2V4V5V8V3V3V6V6V7第41页/共169页2.广度优先遍历（类似于树的层序遍历）基本思想：访问顶点v；依次访问v的各个未被访问的邻接点v1,v2,vk；分别从v1，v2，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。6.16.1图的逻辑结构图的逻辑结构第42页/共169页广度优先遍历序列?入队序列?出队序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V1第43页/共169页广度优先遍历序列?入队序列?出队序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V2V3V3第44页/共169页广度优先遍历序列?入队序列?出队序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V3V4V4V5V5第45页/共169页广度优先遍历序列?入队序列?出队序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V4V5V5V6V6V7V7第46页/共169页广度优先遍历序列?入队序列?出队序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V8第47页/共169页6.26.2图的存储结构及实现图的存储结构及实现是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。第48页/共169页邻接矩阵（数组表示法）邻接矩阵（数组表示法）基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。6.26.2图的存储结构及实现图的存储结构及实现假设图G(V，E)有n个顶点，则邻接矩阵是一个nn的方阵，定义为：arcij1若(vi,vj)E（或E）0其它第49页/共169页无向图的邻接矩阵的特点？无向图的邻接矩阵6.26.2图的存储结构及实现图的存储结构及实现V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4主对角线为0且一定是对称矩阵。第50页/共169页如何求顶点i的度？无向图的邻接矩阵6.26.2图的存储结构及实现图的存储结构及实现V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4邻接矩阵的第i行（或第i列）非零元素的个数。第51页/共169页如何判断顶点i 和j 之间是否存在边？无向图的邻接矩阵6.26.2图的存储结构及实现图的存储结构及实现V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4测试邻接矩阵中相应位置的元素arcij是否为1。第52页/共169页如何求顶点i 的所有邻接点？无向图的邻接矩阵6.26.2图的存储结构及实现图的存储结构及实现V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4将数组中第i行元素扫描一遍，若arcij为1，则顶点j为顶点i 的邻接点。第53页/共169页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4有向图的邻接矩阵一定不对称吗？不一定，例如有向完全图。第54页/共169页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求顶点i 的出度？邻接矩阵的第i 行元素之和。第55页/共169页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求顶点i 的入度？邻接矩阵的第i 列元素之和。第56页/共169页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何判断从顶点i 到顶点j 是否存在边？测试邻接矩阵中相应位置的元素arcij是否为1。第57页/共169页网图的邻接矩阵6.26.2图的存储结构及实现图的存储结构及实现网图的邻接矩阵可定义为：arcijwij若(vi,vj)E（或E）0若i=j其他V1V2V3V4278502500870arc=第58页/共169页邻接矩阵存储无向图的类constintMaxSize=10;templateclassMgraphpublic:MGraph(Ta,intn,inte);MGraph()voidDFSTraverse(intv);voidBFSTraverse(intv);private:TvertexMaxSize;intarcMaxSizeMaxSize;intvertexNum,arcNum;6.26.2图的存储结构及实现图的存储结构及实现第59页/共169页邻接矩阵中图的基本操作构造函数 1.确定图的顶点个数和边的个数；2.输入顶点信息存储在一维数组vertex中；3.初始化邻接矩阵；4.依次输入每条边存储在邻接矩阵arc中；4.1 输入边依附的两个顶点的序号i,j；4.2 将邻接矩阵的第i行第j列的元素值置为1；4.3 将邻接矩阵的第j行第i列的元素值置为1；6.26.2图的存储结构及实现图的存储结构及实现第60页/共169页templateMGraph:MGraph(Ta,intn,inte)vertexNum=n;arcNum=e;for(i=0;ivertexNum;i+)vertexi=ai;for(i=0;ivertexNum;i+)/初始化邻接矩阵for(j=0;jvertexNum;j+)arcij=0;for(k=0;kij;/边依附的两个顶点的序号arcij=1;arcji=1;/置有边标志6.26.2图的存储结构及实现图的存储结构及实现邻接矩阵中图的基本操作构造函数 第61页/共169页1.深度优先遍历（类似于树的前序遍历）基本思想：访问顶点v；从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。6.26.2图的存储结构及实现图的存储结构及实现第62页/共169页邻接矩阵中图的基本操作深度优先遍历templatevoidMGraph:DFSTraverse(intv)coutvertexv;visitedv=1;for(j=0;jvertexNum;j+)if(arcvj=1&visitedj=0)DFSTraverse(j);6.26.2图的存储结构及实现图的存储结构及实现第63页/共169页2.广度优先遍历（类似于树的层序遍历）基本思想：访问顶点v；依次访问v的各个未被访问的邻接点v1,v2,vk；分别从v1，v2，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。6.26.2图的存储结构及实现图的存储结构及实现第64页/共169页邻接矩阵中图的基本操作广度优先遍历templatevoidMGraph:BFSTraverse(intv)front=rear=-1;/假设采用顺序队列且不会发生溢出coutvertexv;visitedv=1;Q+rear=v;while(front!=rear)v=Q+front;/将队头元素出队并送入v中for(j=0;jvertexNum;j+)if(arcvj=1&visitedj=0)coutvertexj;visitedj=1;Q+rear=j;6.26.2图的存储结构及实现图的存储结构及实现第65页/共169页6.26.2图的存储结构及实现图的存储结构及实现图的邻接矩阵存储结构的空间复杂度？如果为稀疏图则会出现什么现象？假设图G有n个顶点e条边，则存储该图需要O(n2)。当图中的边数en2时，图的邻接矩阵变成稀疏矩阵，存储利用率很低。为此，可以改用邻接表。第66页/共169页邻接表邻接表邻接表存储的基本思想：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。6.26.2图的存储结构及实现图的存储结构及实现第67页/共169页邻接表有两种结点结构：顶点表结点和边表结点。vertexfirstedgeadjvexnext顶点表边表vertex：数据域，存放顶点信息。firstedge：指针域，指向边表中第一个结点。adjvex：邻接点域，边的终点在顶点表中的下标。next：指针域，指向边表中的下一个结点。6.26.2图的存储结构及实现图的存储结构及实现第68页/共169页structArcNodeintadjvex;ArcNode*next;templatestructVertexNodeTvertex;ArcNode*firstedge;定义邻接表的结点6.26.2图的存储结构及实现图的存储结构及实现vertexfirstedgeadjvexnext第69页/共169页10323101V1V2V3V40123vertexfirstedge6.26.2图的存储结构及实现图的存储结构及实现V1V3V4V2无向图的邻接表边表中的结点表示什么？每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。第70页/共169页10323101V1V2V3V40123vertexfirstedge6.26.2图的存储结构及实现图的存储结构及实现V1V3V4V2无向图的邻接表如何求顶点i 的度？顶点i的边表中结点的个数。第71页/共169页如何判断顶点i 和顶点j之间是否存在边?测试顶点i 的边表中是否存在终点为j 的结点。6.26.2图的存储结构及实现图的存储结构及实现10323101V1V2V3V40123vertexfirstedgeV1V3V4V2无向图的邻接表第72页/共169页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接表V1V2V3V41220V1V2V3V40123vertexfirstedge如何求顶点i 的出度？顶点i 的出边表中结点的个数。第73页/共169页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接表V1V2V3V41230V1V2V3V40123vertexfirstedge如何求顶点i 的入度？各顶点的出边表中以顶点i 为终点的结点个数。第74页/共169页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接表V1V2V3V41230V1V2V3V40123vertexfirstedge如何求顶点i 的所有邻接点？遍历顶点i 的边表，该边表中的所有终点都是顶点i 的邻接点。第75页/共169页6.26.2图的存储结构及实现图的存储结构及实现网图的邻接表V1V2V3V4278521V1V2V3V40123vertexfirstedge528370对于网图，其边表还需增设一个存储边上信息（如：权值info）的域。Info adjvex第76页/共169页邻接表存储图的类constintMaxSize=10;/图的最大顶点数templateclassALGraphpublic:ALGraph(Ta,intn,inte);ALGraph;voidDFSTraverse(intv);voidBFSTraverse(intv);private:VertexNodeadjlistMaxSize;intvertexNum,arcNum;6.26.2图的存储结构及实现图的存储结构及实现第77页/共169页邻接表中图的基本操作构造函数1.确定图的顶点个数和边的个数；2.输入顶点信息，初始化该顶点的边表；3.依次输入边的信息并存储在边表中；3.1输入边所依附的两个顶点的序号i和j；3.2生成邻接点序号为j的边表结点s；3.3 将结点s插入到第i个边表的头部；6.26.2图的存储结构及实现图的存储结构及实现第78页/共169页templateALGraph:ALGraph(Ta,intn,inte)vertexNum=n;arcNum=e;for(i=0;ivertexNum;i+)/输入顶点信息，初始化边表adjlisti.vertex=ai;adjlisti.firstedge=NULL;6.26.2图的存储结构及实现图的存储结构及实现邻接表中图的基本操作构造函数第79页/共169页for(k=0;kij;ArcNode*s=newArcNode;s-adjvex=j;s-next=adjlisti.firstedge;adjlisti.firstedge=s;6.26.2图的存储结构及实现图的存储结构及实现s12V1V2V3V40123第80页/共169页邻接表中图的基本操作深度优先遍历templatevoidALGraph:DFSTraverse(intv)coutadjvex;if(visitedj=0)DFSTraverse(j);p=p-next;6.26.2图的存储结构及实现图的存储结构及实现第81页/共169页邻接表中图的基本操作广度优先遍历templatevoidALGraph:BFSTraverse(intv)intfront=rear=-1;ArcNode*p;intQMaxSize;coutadjvex;if(visitedj=0)coutnext;6.26.2图的存储结构及实现图的存储结构及实现第82页/共169页图的存储结构的比较图的存储结构的比较邻接矩阵和邻接表邻接矩阵和邻接表O（n2）O（n+e）O（n2）O（n+e）空间性能 时间性能 适用范围 唯一性邻接矩阵邻接表稠密图稀疏图唯一不唯一6.26.2图的存储结构及实现图的存储结构及实现第83页/共169页十字链表十字链表 邻接表6.26.2图的存储结构及实现图的存储结构及实现逆邻接表将邻接表与逆邻接表合二为一?为什么要合并？V1V2V3V41230v1v2v3v401231302v1v2v3v4012303第84页/共169页十字链表的结点结构vertexfirstinfirstout顶点表结点tailvex headvex headlink taillink边表结点tailvex：弧的起点在顶点表中的下标；headvex：弧的终点在顶点表中的下标；headlink：入边表指针域；taillink：出边表指针域。6.26.2图的存储结构及实现图的存储结构及实现vertex：数据域，存放顶点信息；firstin：入边表头指针；firstout：出边表头指针；第85页/共169页30313210V1V2V3V42301026.26.2图的存储结构及实现图的存储结构及实现十字链表存储有向图十字链表存储有向图 V1V2V3V4v3v4v4v1v1v2v1v3v4v2第86页/共169页6.36.3图的连通性图的连通性要想判定一个无向图是否为连通图，或有几个连通分量，通过对无向图遍历即可得到结果。非连通图：需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。连通图：仅需从图中任一顶点出发，进行深度优先搜索（或广度优先搜索），便可访问到图中所有顶点。无向图的连通性无向图的连通性参见P205、图6-24非连通图及连通分量。第87页/共169页1.count=0;2.for(图中每个顶点v)2.1if(v尚未被访问过)2.1.1count+;2.1.2从v出发遍历该图；3.if(count=1)cout图是连通的;elsecout图中有count个连通分量;求无向图的连通分量6.36.3图的连通性图的连通性第88页/共169页有向图的连通性有向图的连通性从某顶点出发进行深度优先遍历，并按其所有邻接点都访问（即出栈）的顺序将顶点排列起来。从最后完成访问的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历。若不能访问到所有顶点，则从余下的顶点中最后访问的那个顶点出发，继续作逆向的深度优先遍历，直至有向图中所有顶点都被访问到为止。每一次逆向深度优先遍历所访问到的顶点集便是该有向图的一个强连通分量的顶点集。6.36.3图的连通性图的连通性第89页/共169页 生成树可以在图的遍历过程中得到。6.36.3图的连通性图的连通性生成树生成树 从连通图G=(V,E)中任一顶点出发进行遍历，必定将边集E分成两个集合T和B，其中T是遍历过程中经历的边的集合，B是剩余的边的集合。显然，T和图G中所有顶点一起构成连通图G的一颗生成树。第90页/共169页（a）深度优先生成树（b）广度优先生成树生成树生成树6.36.3图的连通性图的连通性V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V8第91页/共169页由深度优先遍历得到的为深度优先生成树，一个连通图的生成树可能不唯一，由不同的遍历次序、从不同顶点出发进行遍历都会得到不同的生成树。即：只要能连通所有顶点而又不产生回路的子图都是它的生成树。对于非连通图，通过图的遍历，将得到的是生成森林。结论：6.36.3图的连通性图的连通性生成树生成树由广度优先遍历得到的为广度优先生成树。第92页/共169页生成树的代价：设G=（V，E）是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。应用举例应用举例最小生成树最小生成树最小生成树最小生成树最小生成树的概念可以应用到许多实际问题中。例：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？最小生成树具有MST性质。第93页/共169页MST性质假设G=(V,E)是一个无向连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中uU，vVU，则必存在一棵包含边(u,v)的最小生成树。应用举例应用举例最小生成树最小生成树顶点集UVUuvvu顶点集T1T2第94页/共169页基本思想：设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是G的最小生成树，T的初始状态为U=u0（u0V），TE=，重复执行下述操作：在所有uU，vV-U的边中找一条代价最小的边(u,v)并入集合TE，同时v并入U，直至U=V为止。此时TE中必有n-1条边，T就是最小生成树。关键:是如何找到连接U和V-U的最短边。普里姆（Prim）算法应用举例应用举例最小生成树最小生成树利用MST性质，可以用下述方法构造候选最短边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。第95页/共169页U=AV-U=B,C,D,E,Fcost=(A,B)34,(A,C)46,(A,D),(A,E),(A,F)19251234192646381725应用举例应用举例最小生成树最小生成树ABEDCFPrim算法第96页/共169页Prim算法应用举例应用举例最小生成树最小生成树251234192646381725ABEDCFU=A,FV-U=B,C,D,Ecost=(A,B)34,(F,C)25,(F,D)25,(F,E)26第97页/共169页Prim算法应用举例应用举例最小生成树最小生成树251234192646381725ABEDCFU=A,F,CV-U=B,D,Ecost=(A,B)34,(C,D)17,(F,E)26第98页/共169页Prim算法应用举例应用举例最小生成树最小生成树251234192646381725ABEDCFU=A,F,C,DV-U=B,Ecost=(A,B)34,(F,E)26第99页/共169页Prim算法应用举例应用举例最小生成树最小生成树251234192646381725ABEDCFU=A,F,C,D,EV-U=Bcost=(E,B)12第100页/共169页Prim算法应用举例应用举例最小生成树最小生成树251234192646381725ABEDCFU=A,F,C,D,E,BV-U=第101页/共169页数组lowcostn：用来保存集合V-U中各顶点与集合U中顶点最短边的权值，lowcostv=0表示顶点v已加入最小生成树中；数组adjvexn：用来保存依附于该边（集合V-U中各顶点与集合U中顶点的最短边）在集合U中的顶点。数据结构设计表示顶点vi和顶点vk之间的权值为w，其中：viV-U 且vk U lowcosti=wadjvexi=k应用举例应用举例最小生成树最小生成树如何用数组lowcost和adjvex表示候选最短边集？第102页/共169页i数组B(i=1)C(i=2)D(i=3)E(i=4)F(i=5)UV-U输出adjvexlowcostA34A46AAA19AB,C,D,E,F(AF)19adjvexlowcostA34F25F25F26A,FB,C,D,E(FC)25adjvexlowcostA34C17F26A,F,CB,D,E(CD)17adjvexlowcostA34F26A,F,C,D B,E(FE)26adjvexlowcostE12A,F,C,D,EB(EB)12adjvexlowcostA,F,C,D,E,B应用举例应用举例最小生成树最小生成树第103页/共169页1.初始化两个辅助数组lowcost和adjvex；2.输出顶点u0，将顶点u0加入集合U中；3.重复执行下列操作n-1次3.1在lowcost中选取最短边，取adjvex中对应的顶点序号k；3.2
