数据结构王红梅图.pptx

欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他一生共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。欧拉对著名的哥尼斯堡七桥问题的解答开创了图论的研究。图论欧拉第1页/共167页能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？哥尼斯堡七桥问题第2页/共167页CADB七桥问题的图模型哥尼斯堡七桥问题欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。第3页/共167页图的定义图的定义6.16.1图的逻辑结构图的逻辑结构图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。第4页/共167页6.16.1图的逻辑结构图的逻辑结构如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为。如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。V0V1V2V3V4V0V1V2V3第5页/共167页6.16.1图的逻辑结构图的逻辑结构图的基本术语简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。非简单图 非简单图 简单图v 数据结构中讨论的都是简单图。V0V1V2V3V4V0V1V2V3V4V0V1V2V3V4第6页/共167页6.16.1图的逻辑结构图的逻辑结构图的基本术语邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。V0的邻接点：V1、V3V1的邻接点：V0、V2、V4V0V1V2V3V4第7页/共167页6.16.1图的逻辑结构图的逻辑结构图的基本术语邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧依附于顶点vi和顶点vj。V0V1V2V3V0的邻接点：V1、V2V2的邻接点：V3第8页/共167页在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。FECBAD线性结构ABCDEF树结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比V0V1V2V3V4图结构第9页/共167页在线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。FECBAD线性结构ABCDEF树结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比V0V1V2V3V4图结构第10页/共167页无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。图的基本术语V0V1V2V0V1V2V36.16.1图的逻辑结构图的逻辑结构第11页/共167页含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？6.16.1图的逻辑结构图的逻辑结构含有n个顶点的无向完全图有n(n-1)/2条边。含有n个顶点的有向完全图有n(n-1)条边。V0V1V2V3V0V1V2第12页/共167页稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。6.16.1图的逻辑结构图的逻辑结构图的基本术语顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。第13页/共167页6.16.1图的逻辑结构图的逻辑结构图的基本术语在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？=niievTD12)(V0V1V2V3V4第14页/共167页V0V1V2V36.16.1图的逻辑结构图的逻辑结构图的基本术语在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？evODvIDiiii=11)()(nn第15页/共167页权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。6.16.1图的逻辑结构图的逻辑结构图的基本术语V0V1V2V32785哈夫曼树中的权与网图的权有何区别？7423第16页/共167页路径：在无向图G=(V,E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,vim=vq)，其中，(vij-1,vij)E（1jm）。若G是有向图，则路径也是有方向的，顶点序列满足E。6.16.1图的逻辑结构图的逻辑结构图的基本术语一般情况下，图中的路径不惟一V0到V3的路径：V0V3V0V1V2V3 V0V1V4V2V3V0V1V2V3V4第17页/共167页路径长度：6.16.1图的逻辑结构图的逻辑结构图的基本术语非带权图路径上边的个数带权图路径上各边的权之和V0V3：长度为1V0V1V2V3：长度为3V0V1V4V2V3：长度为4V0V1V2V3V4第18页/共167页路径长度：6.16.1图的逻辑结构图的逻辑结构图的基本术语非带权图路径上边的个数带权图路径上各边的权之和V0V3：长度为8V0V1V2V3：长度为7V0V1V4V2V3：长度为15V0V1V2V3V4256328第19页/共167页回路（环）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。6.16.1图的逻辑结构图的逻辑结构图的基本术语V0V1V2V3V4V0V1V2V3第20页/共167页子图：若图G=（V，E），G=（V，E），如果VV且EE，则称图G是G的子图。6.16.1图的逻辑结构图的逻辑结构图的基本术语V0V1V2V3V4V0V1V2V3V4V0V2V3第21页/共167页连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图的极大连通子图称为连通分量。6.16.1图的逻辑结构图的逻辑结构图的基本术语如何求得一个非连通图的连通分量?1.含有极大顶点数；2.依附于这些顶点的所有边。第22页/共167页连通分量16.16.1图的逻辑结构图的逻辑结构V0V1V3V4V2V6V5V0V1V4V2V3V6V5连通分量2图的基本术语连通分量是对无向图的一种划分第23页/共167页强连通图：在有向图中，对图中任意一对顶点vi和vj(ij)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。6.16.1图的逻辑结构图的逻辑结构图的基本术语如何求得一个非连通图的连通分量?第24页/共167页6.16.1图的逻辑结构图的逻辑结构图的基本术语V0V1V2V3强连通分量1强连通分量2V0V2V3V1第25页/共167页生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。如何理解极小连通子图?6.16.1图的逻辑结构图的逻辑结构图的基本术语多构成回路少不连通含有n-1条边第26页/共167页V0V1V3V4V2V6V5V0V1V3V4V2V6V5V0V1V2V3V4V0V1V2V3V4生成树生成森林6.16.1图的逻辑结构图的逻辑结构第27页/共167页图的抽象数据类型定义图的抽象数据类型定义 ADTGraphData顶点的有穷非空集合和边的集合Operation6.16.1图的逻辑结构图的逻辑结构图是一种与具体应用密切相关的数据结构，它的基本操作往往随应用不同而有很大差别。下面给出一个图的抽象数据类型定义的例子，简单起见，基本操作仅包含图的遍历，针对具体应用，需要重新定义其基本操作。第28页/共167页InitGraph前置条件：图不存在输入：无功能：图的初始化输出：无后置条件：构造一个空的图DestroyGraph前置条件：图已存在输入：无功能：销毁图输出：无后置条件：释放图所占用的存储空间6.16.1图的逻辑结构图的逻辑结构第29页/共167页DFSTraverse前置条件：图已存在输入：遍历的起始顶点v功能：从顶点v出发深度优先遍历图输出：图中顶点的一个线性排列后置条件：图保持不变BFSTraverse前置条件：图已存在输入：遍历的起始顶点v功能：从顶点v出发广度优先遍历图输出：图中顶点的一个线性排列后置条件：图保持不变endADT6.16.1图的逻辑结构图的逻辑结构第30页/共167页图的遍历操作图的遍历操作图的遍历是在从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。6.16.1图的逻辑结构图的逻辑结构抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。第31页/共167页图的遍历操作要解决的关键问题在图中，如何选取遍历的起始顶点？6.16.1图的逻辑结构图的逻辑结构n在线性表中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的；n在树中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；n在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。解决方案：从编号小的顶点开始。第32页/共167页从某个起点始可能到达不了所有其它顶点，怎么办？6.16.1图的逻辑结构图的逻辑结构图的遍历操作要解决的关键问题解决方案：多次调用从某顶点出发遍历图的算法。v下面仅讨论从某顶点出发遍历图的算法。第33页/共167页因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环。在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？6.16.1图的逻辑结构图的逻辑结构图的遍历操作要解决的关键问题解决方案：附设访问标志数组visitedn。解决方案：深度优先遍历和广度优先遍历。第34页/共167页约翰霍普克洛夫特1939年生于西雅图。1961年进入斯坦福大学研究生院深造，1962年获硕士学位，1964年获博士学位。毕业后先后在普林斯顿大学、斯坦福大学等著名学府工作，也曾任职于一些科学研究机构如 NSF（美国科学基金会）和 NRC（美国国家研究院）。罗伯特陶尔扬1948年4月30日生于加利福尼亚州。1969年本科毕业，进入斯坦福大学研究生院，1972年获得博士学位。1986年图灵奖获得者6.16.1图的逻辑结构图的逻辑结构第35页/共167页1.深度优先遍历基本思想：访问顶点v；从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。6.16.1图的逻辑结构图的逻辑结构第36页/共167页深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8V1遍历序列：V1V2V2V4V4V5V5第37页/共167页深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8V1遍历序列：V1V2V2V4V4V5V8V8第38页/共167页深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8V1遍历序列：V1V2V2V4V4V5V8第39页/共167页深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8V1遍历序列：V1V7V2V4V5V8V3V3V6V6V7第40页/共167页1.深度优先遍历从顶点v出发图的深度优先遍历算法的伪代码：6.16.1图的逻辑结构图的逻辑结构1.访问顶点v;visitedv=1;2.w=顶点v的第一个邻接点；3.while(w存在)3.1if(w未被访问)从顶点w出发递归执行该算法;3.2w=顶点v的下一个邻接点;第41页/共167页2.广度优先遍历基本思想：访问顶点v；依次访问v的各个未被访问的邻接点v1,v2,vk；分别从v1，v2，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。6.16.1图的逻辑结构图的逻辑结构第42页/共167页广度优先遍历序列?入队序列?出队序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V1第43页/共167页广度优先遍历序列?入队序列?出队序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V2V3V3第44页/共167页广度优先遍历序列?入队序列?出队序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V3V4V4V5V5第45页/共167页广度优先遍历序列?入队序列?出队序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V4V5V5V6V6V7V7第46页/共167页广度优先遍历序列?入队序列?出队序列?6.16.1图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V8第47页/共167页2.广度优先遍历6.16.1图的逻辑结构图的逻辑结构从顶点v出发图的广度优先遍历算法的伪代码：1.初始化队列Q;2.访问顶点v;visitedv=1;顶点v入队列Q;3.while(队列Q非空)3.1v=队列Q的队头元素出队;3.2w=顶点v的第一个邻接点;3.3while(w存在)3.3.1如果w未被访问，则访问顶点w;visitedw=1;顶点w入队列Q；3.3.2w=顶点v的下一个邻接点；第48页/共167页6.26.2图的存储结构及实现图的存储结构及实现是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。第49页/共167页邻接矩阵（数组表示法）邻接矩阵（数组表示法）基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。6.26.2图的存储结构及实现图的存储结构及实现假设图G(V，E)有n个顶点，则邻接矩阵是一个nn的方阵，定义为：arcij1若(vi,vj)E（或E）0其它第50页/共167页无向图的邻接矩阵的特点？无向图的邻接矩阵6.26.2图的存储结构及实现图的存储结构及实现V0V2V3V1V0 V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3主对角线为0且一定是对称矩阵。第51页/共167页如何求顶点i的度？无向图的邻接矩阵6.26.2图的存储结构及实现图的存储结构及实现邻接矩阵的第i行（或第i列）非零元素的个数。0101101101001100arc=V0V1V2V3V0V1V2V3V0V2V3V1V0 V1V2V3vertex=第52页/共167页如何判断顶点i 和j 之间是否存在边？无向图的邻接矩阵6.26.2图的存储结构及实现图的存储结构及实现测试邻接矩阵中相应位置的元素arcij是否为1。0101101101001100arc=V0V1V2V3V0V1V2V3V0V2V3V1V0 V1V2V3vertex=第53页/共167页如何求顶点i 的所有邻接点？无向图的邻接矩阵6.26.2图的存储结构及实现图的存储结构及实现将数组中第i行元素扫描一遍，若arcij为1，则顶点j为顶点i 的邻接点。V0V2V3V10101101101001100arc=V0V1V2V3V0V1V2V3V0 V1V2V3vertex=第54页/共167页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接矩阵V0V1V2V3V0 V1V2V3vertex=0110000000011000arc=V0 V1V2V3V0V1V2V3有向图的邻接矩阵一定不对称吗？不一定，例如有向完全图。第55页/共167页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接矩阵如何求顶点i 的出度？邻接矩阵的第i 行元素之和。V0V1V2V3V0 V1V2V3vertex=0110000000011000arc=V0 V1V2V3V0V1V2V3第56页/共167页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接矩阵如何求顶点i 的入度？邻接矩阵的第i 列元素之和。V0V1V2V3V0 V1V2V3vertex=0110000000011000arc=V0 V1V2V3V0V1V2V3第57页/共167页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接矩阵如何判断从顶点i 到顶点j 是否存在边？测试邻接矩阵中相应位置的元素arcij是否为1。V0V1V2V3V0 V1V2V3vertex=0110000000011000arc=V0 V1V2V3V0V1V2V3第58页/共167页网图的邻接矩阵6.26.2图的存储结构及实现图的存储结构及实现网图的邻接矩阵可定义为：arcijwij若(vi,vj)E（或E）0若i=j其他V0V1V2V3278502500870arc=第59页/共167页邻接矩阵存储无向图的类constintMaxSize=10;templateclassMgraphpublic:MGraph(DataTypea,intn,inte);MGraph()voidDFSTraverse(intv);voidBFSTraverse(intv);private:DataTypevertexMaxSize;intarcMaxSizeMaxSize;intvertexNum,arcNum;6.26.2图的存储结构及实现图的存储结构及实现第60页/共167页邻接矩阵中图的基本操作构造函数 1.确定图的顶点个数和边的个数；2.输入顶点信息存储在一维数组vertex中；3.初始化邻接矩阵；4.依次输入每条边存储在邻接矩阵arc中；4.1输入边依附的两个顶点的序号i,j；4.2将邻接矩阵的第i行第j列的元素值置为1；4.3将邻接矩阵的第j行第i列的元素值置为1；6.26.2图的存储结构及实现图的存储结构及实现第61页/共167页template MGraph:MGraph(DataType a,int n,int e)vertexNum=n;arcNum=e;for(i=0;i vertexNum;i+)vertexi=ai;for(i=0;i vertexNum;i+)/初始化邻接矩阵 for(j=0;j vertexNum;j+)arcij=0;for(k=0;k i j;/输入边依附的两个顶点的编号 arcij=1;arcji=1;/置有边标志 6.26.2图的存储结构及实现图的存储结构及实现邻接矩阵中图的基本操作构造函数 第62页/共167页邻接矩阵中图的基本操作深度优先遍历templatevoidMGraph:DFSTraverse(intv)coutvertexv;visitedv=1;for(j=0;jvertexNum;j+)if(arcvj=1&visitedj=0)DFSTraverse(j);6.26.2图的存储结构及实现图的存储结构及实现第63页/共167页邻接矩阵中图的基本操作广度优先遍历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图的存储结构及实现图的存储结构及实现第64页/共167页邻接表邻接表邻接表存储的基本思想：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。6.26.2图的存储结构及实现图的存储结构及实现图的邻接矩阵存储结构的空间复杂度？如果为稀疏图则会出现什么现象？假设图G有n个顶点e条边，则存储该图需要O(n2)。第65页/共167页邻接表有两种结点结构：顶点表结点和边表结点。vertexfirstedgeadjvexnext顶点表边表vertex：数据域，存放顶点信息。firstedge：指针域，指向边表中第一个结点。adjvex：邻接点域，边的终点在顶点表中的下标。next：指针域，指向边表中的下一个结点。6.26.2图的存储结构及实现图的存储结构及实现第66页/共167页structArcNodeintadjvex;ArcNode*next;templatestructVertexNodeDataTypevertex;ArcNode*firstedge;定义邻接表的结点6.26.2图的存储结构及实现图的存储结构及实现vertexfirstedgeadjvexnext第67页/共167页10323101V0V1V2V30123vertexfirstedge6.26.2图的存储结构及实现图的存储结构及实现V0V2V3V1无向图的邻接表边表中的结点表示什么？每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。第68页/共167页6.26.2图的存储结构及实现图的存储结构及实现无向图的邻接表如何求顶点i 的度？顶点i的边表中结点的个数。V0V2V3V110323101V0V1V2V30123vertexfirstedge第69页/共167页如何判断顶点i 和顶点j之间是否存在边?测试顶点i 的边表中是否存在终点为j 的结点。6.26.2图的存储结构及实现图的存储结构及实现无向图的邻接表V0V2V3V110323101V0V1V2V30123vertexfirstedge第70页/共167页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接表V0V1V2V31220V0V1V2V30123vertexfirstedge如何求顶点i 的出度？顶点i 的出边表中结点的个数。第71页/共167页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接表如何求顶点i 的入度？各顶点的出边表中以顶点i 为终点的结点个数。V0V1V2V31220V0V1V2V30123vertexfirstedge第72页/共167页6.26.2图的存储结构及实现图的存储结构及实现有向图的邻接表如何求顶点i 的所有邻接点？遍历顶点i 的边表，该边表中的所有终点都是顶点i 的邻接点。V0V1V2V31220V0V1V2V30123vertexfirstedge第73页/共167页6.26.2图的存储结构及实现图的存储结构及实现网图的邻接表V0V1V2V3278521V0V1V2V30123vertexfirstedge528370第74页/共167页邻接表存储有向图的类constintMaxSize=10;/图的最大顶点数templateclassALGraphpublic:ALGraph(DataTypea,intn,inte);ALGraph;voidDFSTraverse(intv);voidBFSTraverse(intv);private:VertexNodeadjlistMaxSize;intvertexNum,arcNum;6.26.2图的存储结构及实现图的存储结构及实现第75页/共167页邻接表中图的基本操作构造函数1.确定图的顶点个数和边的个数；2.输入顶点信息，初始化该顶点的边表；3.依次输入边的信息并存储在边表中；3.1输入边所依附的两个顶点的序号i和j；3.2生成邻接点序号为j的边表结点s；3.3 将结点s插入到第i个边表的头部；6.26.2图的存储结构及实现图的存储结构及实现第76页/共167页templateALGraph:ALGraph(DataTypea,intn,inte)vertexNum=n;arcNum=e;for(i=0;ivertexNum;i+)/输入顶点信息，初始化顶点表adjlisti.vertex=ai;adjlisti.firstedge=NULL;6.26.2图的存储结构及实现图的存储结构及实现邻接表中图的基本操作构造函数第77页/共167页sfor(k=0;kij;s=newArcNode;s-adjvex=j;s-next=adjlisti.firstedge;adjlisti.firstedge=s;6.26.2图的存储结构及实现图的存储结构及实现12V0V1V2V30123邻接表中图的基本操作构造函数第78页/共167页邻接表中图的基本操作深度优先遍历templatevoidALGraph:DFSTraverse(intv)coutadjvex;if(visitedj=0)DFSTraverse(j);p=p-next;6.26.2图的存储结构及实现图的存储结构及实现第79页/共167页邻接表中图的基本操作广度优先遍历templatevoidALGraph:BFSTraverse(intv)front=rear=-1;/初始化顺序队列coutadjvex;if(visitedj=0)coutnext;6.26.2图的存储结构及实现图的存储结构及实现第80页/共167页十字链表十字链表 邻接表6.26.2图的存储结构及实现图的存储结构及实现逆邻接表将邻接表与逆邻接表合二为一?为什么要合并？V0V1V2V31230v0v1v2v301231302v0v1v2v3012303第81页/共167页十字链表的结点结构vertexfirstinfirstout顶点表结点tailvex headvex headlink taillink边表结点tailvex：弧的起点在顶点表中的下标；headvex：弧的终点在顶点表中的下标；headlink：入边表指针域；taillink：出边表指针域。6.26.2图的存储结构及实现图的存储结构及实现vertex：数据域，存放顶点信息；firstin：入边表头指针；firstout：出边表头指针；第82页/共167页30313210V0V1V2V32301026.26.2图的存储结构及实现图的存储结构及实现十字链表存储有向图十字链表存储有向图 V0V1V2V3v2v3v3v0v0v1v0v2v3v1第83页/共167页6.26.2图的存储结构及实现图的存储结构及实现邻接多重表存储无向图邻接多重表存储无向图 ivexilinkjvexjlinkvertexfirstedge(a)顶点表结点(b)边表结点vertex：数据域，存储有关顶点的数据信息；firstedge：边表头指针，指向依附于该顶点的边表；ivex、jvex：与某条边依附的两个顶点在顶点表中的下标；ilink：指针域，指向依附于顶点ivex的下一条边；jlink：指针域，指向依附于顶点jvex的下一条边。第84页/共167页6.26.2图的存储结构及实现图的存储结构及实现邻接多重表存储无向图邻接多重表存储无向图 V0V2V3V1第85页/共167页图的存储结构的比较图的存储结构的比较邻接矩阵和邻接表邻接矩阵和邻接表O（n2）O（n+e）O（n2）O（n+e）空间性能 时间性能 适用范围 唯一性邻接矩阵邻接表稠密图稀疏图唯一不唯一6.26.2图的存储结构及实现图的存储结构及实现第86页/共167页p生成树的代价：设G=(V,E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。p最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。6.36.3最小生成树最小生成树最小生成树的定义最小生成树的定义最小生成树的概念可以应用到许多实际问题中。例：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？第87页/共167页MST性质假设G=(V,E)是一个无向连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中uU，vVU，则必存在一棵包含边(u,v)的最小生成树。顶点集UVUuvvu顶点集T1T26.36.3最小生成树最小生成树第88页/共167页基本思想：设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是G的最小生成树，T的初始状态为U=u0（u0V），TE=，重复执行下述操作：在所有uU，vV-U的边中找一条代价最小的边(u,v)并入集合TE，同时v并入U，直至U=V。普里姆（Prim）算法6.36.3最小生成树最小生成树Prim算法的基本思想用伪代码描述如下：1.初始化：U=v0；TE=；2.重复下述操作直到U=V：2.1在E中寻找最短边(u，v)，且满足uU，vV-U；2.2U=U+v；2.3TE=TE+(u，v)；关键:是如何找到连接U和V-U的最短边。第89页/共167页U=AV-U=B,C,D,E,Fcost=(A,B)34,(A,C)46,(A,D),(A,E),(A,F)19251234192646381725ABEDCFPrim算法6.36.3最小生成树最小生成树第90页/共167页Prim算法251234192646381725ABEDCFU=A,FV-U=B,C,D,Ecost=(A,B)34,(F,C)25,(F,D)25,(F,E)266.36.3最小生成树最小生成树第91页/共167页Prim算法2512341926381725ABEDCFU=A,F,CV-U=B,D,Ecost=(A,B)34,(C,D)17,(F,E)266.36.3最小生成树最小生成树第92页/共167页Prim算法12341926381725ABEDCFU=A,F,C,DV-U=B,Ecost=(A,B)34,(F,E)266.36.3最小生成树最小生成树第93页/共167页Prim算法123419261725ABEDCFU=A,F,C,D,EV-U=Bcost=(E,B)126.36.3最小生成树最小生成树第94页/共167页Prim算法1219261725ABEDCFU=A,F,C,D,E,BV-U=6.36.3最小生成树最小生成树第95页/共167页1.图的存储结构：由于在算法执行过程中，需要不断读取任意两个顶点之间边的权值，所以，图采用邻接矩阵存储。数据结构设计6.36.3最小生成树最小生成树第96页/共167页251234192646381725ABEDCF对于顶点C，只需保留minarcAC,arcFC6.36.3最小生成树最小生成树2.候选最短边集：设置数组shortEdgen表示候选最短边集，数组元素包括adjvex和lowcost两个域，分别表示候选最短边的邻接点和权值。数据结构设计对于V-U中的每个顶点，只保留从该顶点到U中的某顶点的最短边。第97页/共167页p候选最短边(vi,vk)的权值为w，其中viV-U，vkU：如何用lowcost和adjvex表示候选最短边集？6.36.3最小生成树最小生成树shortEdgei.adjvex=kshortEdgei.lowcost=w数据结构设计shortEdgej.lowcost=minshortEdgej.lowcost,cost(vj，vk)shortEdgej.adjvex=k（如果边(vj，vk)的权值较小）p顶点vk从集合V-U进入集合U后，依据下式更新数组shortEdge：第98页/共167页1.初始化两个辅助数组lowcost和adjvex；2.输出顶点u0，将顶点u0加入集合U中；3.重复执行下列操作n-1次3.1在lowcost中选取最短边，取adjvex中对应的顶点序号k；3.2输出顶点k和对应的权值；3.3将顶点k加入集合U中；3.4调整数组lowcost和adjvex；Prim算法伪代码6.36.3最小生成树最小生成树第99页/共167页克鲁斯卡尔（Kruskal）算法基本思想：设无向连通网为G(V,E)，令G的最小生成树为T(U,TE)，其初态为UV，TE，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。6.36.3最小生成树最小生成树第100页/共167页克鲁斯卡尔（Kruskal）算法1.初始化：U=V；TE=；2.重复下述操作直到T中的连通分量个数为1：2.1在E中寻找最短边(u，v);2.2如果顶点u、v位于T的两个不同连通分量，则2.2.1将边(u，v)并入TE；2.2.2将这两个连通分量合为一个；2.3标记边(u，v)，使得(u，v)不参加后续最短边的选取；6.36.3最小生成树最小生成树Kruskal算法的基本思想用伪代码描述如下：关键：如何判别被考察边的两个顶点是否位于两个连通分量 第101页/共167页251234192646381725ABEDCFABEDCF连通分量A,B,C,D,E,F6.36.3最小生成树最小生成树第102页/共167页251234192646381725ABEDCFABEDCF连通分量A,B,C,D,E,F12连通分量A,B,E,C,D,F6.36.3最小生成树最小生成树第103页/共167页251234192646381725ABEDCFABEDCF连通分量A,F,B,E,C,D12连通分量A,F,B,E,C,D176.36.3最小生成树最小生成树第104页/共167页251234192646381725ABEDCFABEDCF连通分量A,B,E,C,D,F12连通分量A,F,B,E,C,D196.36.3最小生成树最小生成树17第105页/共167页251234192646381725ABEDCFABEDCF连通分量A,F,B,E,C,D12连通分量A,F,C,D,B,E1917256.36.3最小生成树最小生成树第106页/共167页251234192646381725ABEDCFABEDCF连通分量A,F,C,D,B,E12连通分量A,F,C,D,B,E191725266.36.3最小生成树最小生成树第107页/共167页6.36.