版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、会计学1数数据结构数数据结构(sh j ji u)图图第一页,共135页。能否从某个地方出发,穿过所有的桥仅一次后再回到出发点?哥尼斯堡七桥问题(wnt) 第1页/共135页第二页,共135页。CADB七桥问题(wnt)的图模型哥尼斯堡七桥问题(wnt) 欧拉回路的判定规则:1.如果通奇数桥的地方多于两个,则不存在欧拉回路;2.如果只有两个地方通奇数桥,可以从这两个地方之一出发,找到欧拉回路;3.如果没有一个(y )地方是通奇数桥的,则无论从哪里出发,都能找到欧拉回路。第2页/共135页第三页,共135页。图的定义(dngy)6.1 图的逻辑(lu j)结构图是由顶点(dngdin)的有穷非空
2、集合和顶点(dngdin)之间边的集合组成,通常表示为: G=(V,E)其中:G表示一个图,V是图G中顶点(dngdin)的集合,E是图G中顶点(dngdin)之间边的集合。 在线性表中,元素个数可以为零,称为空表;在树中,结点个数可以为零,称为空树;在图中,顶点个数不能为零,但可以没有边。第3页/共135页第四页,共135页。6.1 图的逻辑(lu j)结构如果(rgu)图的任意两个顶点之间的边都是无向边,则称该图为无向图。若顶点vi和vj之间的边没有(mi yu)方向,则称这条边为无向边,表示为(vi,vj)。若从顶点vi到vj的边有方向,则称这条边为有向边,表示为。 如果图的任意两个顶点
3、之间的边都是有向边,则称该图为有向图。V1V2V3V4V5V1V2V3V4第4页/共135页第五页,共135页。6.1 图的逻辑(lu j)结构图的基本(jbn)术语 简单(jindn)图:在图中,若不存在顶点到其自身的边,且同一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图 非简单图 简单图V1V2V3V4V5v 数据结构中讨论的都是简单图。第5页/共135页第六页,共135页。6.1 图的逻辑(lu j)结构图的基本(jbn)术语 邻接、依附无向(w xin)图中,对于任意两个顶点vi和顶点vj,若存在边(vi,vj),则称顶点vi和顶点vj互为邻接点,同时称边(vi,v
4、j)依附于顶点vi和顶点vj。V1V2V3V4V5V1的邻接点: V2 、V4V2的邻接点: V1 、V3 、V5第6页/共135页第七页,共135页。6.1 图的逻辑(lu j)结构图的基本(jbn)术语 邻接、依附有向图中,对于任意两个(lin )顶点vi和顶点vj,若存在弧,则称顶点vi邻接到顶点vj,顶点vj邻接自顶点vi,同时称弧依附于顶点vi和顶点vj 。 V1V2V3V4V1的邻接点: V2 、V3V3的邻接点: V4第7页/共135页第八页,共135页。在线性结构中,数据元素之间仅具有线性关系;在树结构中,结点之间具有层次(cngc)关系;在图结构中,任意两个顶点之间都可能有关
5、系。 FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构(jigu)中逻辑关系的对比第8页/共135页第九页,共135页。在线性结构中,元素之间的关系为前驱和后继;在树结构中,结点之间的关系为双亲(shungqn)和孩子;在图结构中,顶点之间的关系为邻接。 FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同(b tn)结构中逻辑关系的对比第9页/共135页第十页,共135页。无向完全(wnqun)图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全(wnqun)图。有向完全图:在有向图中,如果任意两个顶点之间都存在(cnzi)方向相反的两条弧
6、,则称该图为有向完全图。 图的基本(jbn)术语 V1V2V3V1V2V3V46.1 图的逻辑结构第10页/共135页第十一页,共135页。含有n个顶点(dngdin)的无向完全图有多少条边?含有n个顶点(dngdin)的有向完全图有多少条弧? 6.1 图的逻辑(lu j)结构含有(hn yu)n个顶点的无向完全图有n(n-1)/2条边。 含有(hn yu)n个顶点的有向完全图有n(n-1)条边。 V1V2V3V1V2V3V4第11页/共135页第十二页,共135页。稀疏(xsh)图:称边数很少的图为稀疏(xsh)图;稠密图:称边数很多的图为稠密图。顶点(dngdin)的度:在无向图中,顶点(
7、dngdin)v的度是指依附于该顶点(dngdin)的边数,通常记为TD (v)。6.1 图的逻辑(lu j)结构图的基本术语 顶点的入度:在有向图中,顶点v的入度是指以该顶点为弧头的弧的数目,记为ID (v);顶点的出度:在有向图中,顶点v的出度是指以该顶点为弧尾的弧的数目,记为OD (v)。第12页/共135页第十三页,共135页。V1V2V3V4V56.1 图的逻辑(lu j)结构图的基本(jbn)术语 在具有n个顶点、e条边的无向图G中,各顶点的度之和与边数之和的关系?=niievTD12)(第13页/共135页第十四页,共135页。V1V2V3V46.1 图的逻辑(lu j)结构图的
8、基本(jbn)术语 在具有n个顶点、e条边的有向图G中,各顶点的入度之和与各顶点的出度之和的关系?与边数之和的关系?evODvIDiiii=11)()(nn第14页/共135页第十五页,共135页。权:是指对边赋予的有意义(yy)的数值量。网:边上带权的图,也称网图。6.1 图的逻辑(lu j)结构图的基本(jbn)术语 V1V2V3V42785第15页/共135页第十六页,共135页。路径:在无向图G=(V, E)中,从顶点vp到顶点vq之间的路径是一个顶点序列(xli)(vp=vi0,vi1,vi2, , vim=vq),其中,(vij-1,vij)E(1jm)。若G是有向图,则路径也是有
9、方向的,顶点序列(xli)满足E。6.1 图的逻辑(lu j)结构图的基本(jbn)术语 V1V2V3V4V5v一般情况下,图中的路径不惟一。V1 到V4的路径: V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4第16页/共135页第十七页,共135页。6.1 图的逻辑(lu j)结构图的基本(jbn)术语 非带权图路径上边的个数带权图路径上各边的权之和V1V2V3V4V5V1 V4:长度为1V1 V2 V3 V4 :长度为3V1 V2 V5V3 V4 :长度为4第17页/共135页第十八页,共135页。6.1 图的逻辑(lu j)结构图的基本(jbn)术语 非带权图路径上边的个
10、数带权图路径上各边的权之和V1 V4:长度为8V1 V2 V3 V4 :长度为7V1 V2 V5V3 V4 :长度为15V1V2V3V4V5256328第18页/共135页第十九页,共135页。6.1 图的逻辑(lu j)结构图的基本(jbn)术语 V1V2V3V4V5V1V2V3V4第19页/共135页第二十页,共135页。子图:若图G=(V,E),G=(V,E),如果(rgu)VV 且E E ,则称图G是G的子图。6.1 图的逻辑(lu j)结构图的基本(jbn)术语 V1V2V3V4V5V1V2V3V4V5V1V3V4第20页/共135页第二十一页,共135页。连通(lintng)图:在
11、无向图中,如果从一个顶点vi到另一个顶点vj(ij)有路径,则称顶点vi和vj是连通(lintng)的。如果图中任意两个顶点都是连通(lintng)的,则称该图是连通(lintng)图。连通(lintng)分量:非连通(lintng)图的极大连通(lintng)子图称为连通(lintng)分量。 6.1 图的逻辑(lu j)结构图的基本(jbn)术语 如何求得一个非连通图的连通分量?1.含有极大顶点数;2. 依附于这些顶点的所有边。第21页/共135页第二十二页,共135页。连通分量1 6.1 图的逻辑(lu j)结构V1V2V3V4V5V6V7V1V2V4V5V3V6V7连通分量2图的基本(
12、jbn)术语 v连通分量是对无向图的一种(y zhn)划分。第22页/共135页第二十三页,共135页。强连通图:在有向图中,对图中任意(rny)一对顶点vi和vj (ij),若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径,则称该有向图是强连通图。强连通分量:非强连通图的极大强连通子图。 6.1 图的逻辑(lu j)结构图的基本(jbn)术语 如何求得一个非连通图的连通分量?第23页/共135页第二十四页,共135页。6.1 图的逻辑(lu j)结构图的基本(jbn)术语 V1V2V3V4强连通分量1 强连通分量2V1V3V4V2第24页/共135页第二十五页,共135页。生成树:n个顶
13、点(dngdin)的连通图G的生成树是包含G中全部顶点(dngdin)的一个极小连通子图。 生成森林(snln):在非连通图中,由每个连通分量都可以得到一棵生成树,这些连通分量的生成树就组成了一个非连通图的生成森林(snln)。 如何理解极小连通子图?6.1 图的逻辑(lu j)结构图的基本术语 多构成回路少不连通含有n-1条边第25页/共135页第二十六页,共135页。V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成森林6.1 图的逻辑(lu j)结构第26页/共135页第二十七页,共135页。图的抽象数据类型定义(dngy) ADT
14、 GraphData 顶点的有穷非空集合和边的集合Operation InitGraph 前置条件:图不存在 输入:无 功能:图的初始化 输出:无 后置条件:构造(guzo)一个空的图6.1 图的逻辑(lu j)结构第27页/共135页第二十八页,共135页。 DFSTraverse 前置条件(tiojin):图已存在 输入:遍历的起始顶点v 功能:从顶点v出发深度优先遍历图 输出:图中顶点的一个线性排列 后置条件(tiojin):图保持不变 BFSTraverse 前置条件(tiojin):图已存在 输入:遍历的起始顶点v 功能:从顶点v出发广度优先遍历图 输出:图中顶点的一个线性排列 后置
15、条件(tiojin):图保持不变6.1 图的逻辑(lu j)结构第28页/共135页第二十九页,共135页。DestroyGraph 前置条件:图已存在 输入:无 功能:销毁图 输出(shch):无 后置条件:释放图所占用的存储空间GetVex 前置条件:图已存在 输入:顶点v 功能:在图中查找顶点v的数据信息 输出(shch):顶点v的数据信息 后置条件:图保持不变endADT6.1 图的逻辑(lu j)结构第29页/共135页第三十页,共135页。图的遍历(bin l)操作图的遍历是在从图中某一顶点出发(chf),对图中所有顶点访问一次且仅访问一次。 6.1 图的逻辑(lu j)结构抽象操
16、作,可以是对结点进行的各种处理,这里简化为输出结点的数据。第30页/共135页第三十一页,共135页。图的遍历(bin l)操作要解决的关键问题 在图中,如何(rh)选取遍历的起始顶点?6.1 图的逻辑(lu j)结构n在线性表中,数据元素在表中的编号就是元素在序列中的位置,因而其编号是唯一的;n在树中,将结点按层序编号,由于树具有层次性,因而其层序编号也是唯一的;n在图中,任何两个顶点之间都可能存在边,顶点是没有确定的先后次序的,所以,顶点的编号不唯一。为了定义操作的方便,将图中的顶点按任意顺序排列起来,比如,按顶点的存储顺序。解决方案:从编号小的顶点开始 。第31页/共135页第三十二页,
17、共135页。 从某个起点始可能(knng)到达不了所有其它顶点,怎么办?6.1 图的逻辑(lu j)结构图的遍历(bin l)操作要解决的关键问题解决方案:多次调用从某顶点出发遍历图的算法。v下面仅讨论从某顶点出发遍历图的算法。第32页/共135页第三十三页,共135页。 因图中可能存在回路,某些顶点可能会被重复访问,那么如何避免遍历不会因回路而陷入死循环。 在图中,一个(y )顶点可以和其它多个顶点相连,当这样的顶点访问过后,如何选取下一个(y )要访问的顶点? 6.1 图的逻辑(lu j)结构图的遍历(bin l)操作要解决的关键问题解决方案:附设访问标志数组visitedn 。解决方案:
18、深度优先遍历和广度优先遍历。第33页/共135页第三十四页,共135页。约翰霍普克洛夫特1939年生于西雅图。1961年进入(jnr)斯坦福大学研究生院深造,1962年获硕士学位,1964年获博士学位。毕业后先后在普林斯顿大学、斯坦福大学等著名学府工作,也曾任职于一些科学研究机构如 NSF(美国科学基金会)和 NRC(美国国家研究院)。罗伯特陶尔扬1948年4月30日生于加利福尼亚州 。1969年本科毕业,进入(jnr)斯坦福大学研究生院,1972年获得博士学位。1986年图灵奖获得者6.1 图的逻辑(lu j)结构第34页/共135页第三十五页,共135页。1. 深度优先(yuxin)遍历
19、基本(jbn)思想 : 访问顶点v; 从v的未被访问的邻接点中选取一个顶点w,从w出发进行深度优先遍历; 重复上述两步,直至(zhzh)图中所有和v有路径相通的顶点都被访问到。 6.1 图的逻辑结构第35页/共135页第三十六页,共135页。深一层递归递 归 返 回(fnhu)深度优先遍历序列?入栈序列?出栈序列?6.1 图的逻辑(lu j)结构V1V3V2V4V5V6V7V8 V1遍历(bin l)序列:V1V2 V2V4 V4V5 V5第36页/共135页第三十七页,共135页。深一层递归递 归 返 回(fnhu)深度优先遍历序列?入栈序列?出栈序列?6.1 图的逻辑(lu j)结构V1V
20、3V2V4V5V6V7V8 V1遍历(bin l)序列:V1V2 V2V4 V4V5V8 V8第37页/共135页第三十八页,共135页。深一层递归递 归 返 回(fnhu)深度优先遍历序列?入栈序列?出栈序列?6.1 图的逻辑(lu j)结构V1V3V2V4V5V6V7V8 V1遍历(bin l)序列:V1V2 V2V4 V4V5V8第38页/共135页第三十九页,共135页。深一层递归递 归 返 回(fnhu)深度优先遍历序列?入栈序列?出栈序列?6.1 图的逻辑(lu j)结构V1V3V2V4V5V6V7V8 V1遍历(bin l)序列:V1 V7V2V4V5V8V3 V3V6 V6V7
21、第39页/共135页第四十页,共135页。2. 广度优先(yuxin)遍历 基本(jbn)思想: 访问顶点v; 依次访问v的各个未被访问的邻接点v1, v2, , vk; 分别从v1,v2,vk出发依次访问它们(t men)未被访问的邻接点,并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。6.1 图的逻辑结构第40页/共135页第四十一页,共135页。广度优先遍历序列?入队序列?出队序列? 6.1 图的逻辑(lu j)结构V1V3V2V4V5V6V7V8遍历(bin l)序列:V1V1第41页/共135页第四十二页,共135页。广
22、度优先遍历序列?入队序列?出队序列? 6.1 图的逻辑(lu j)结构V1V3V2V4V5V6V7V8遍历(bin l)序列:V1V2V2V3V3第42页/共135页第四十三页,共135页。广度优先遍历序列?入队序列?出队序列? 6.1 图的逻辑(lu j)结构V1V3V2V4V5V6V7V8遍历(bin l)序列:V1V2V3V3V4V4V5V5第43页/共135页第四十四页,共135页。广度优先遍历序列?入队序列?出队序列? 6.1 图的逻辑(lu j)结构V1V3V2V4V5V6V7V8遍历(bin l)序列:V1V2V3V4V4V5V5V6V6V7V7第44页/共135页第四十五页,共
23、135页。广度优先遍历序列?入队序列?出队序列? 6.1 图的逻辑(lu j)结构V1V3V2V4V5V6V7V8遍历(bin l)序列:V1V2V3V4V5V5V6V6V7V7V8V8第45页/共135页第四十六页,共135页。6.2 图的存储结构(jigu)及实现是否可以采用顺序存储结构存储图?图的特点:顶点之间的关系是m:n,即任何两个顶点之间都可能存在关系(边),无法通过存储位置表示(biosh)这种任意的逻辑关系,所以,图无法采用顺序存储结构。如何存储图?考虑(kol)图的定义,图是由顶点和边组成的,分别考虑(kol)如何存储顶点、如何存储边。第46页/共135页第四十七页,共135
24、页。邻接矩阵(数组表示法)基本思想:用一个一维数组存储图中顶点的信息,用一个二维数组(称为邻接(ln ji)矩阵)存储图中各顶点之间的邻接(ln ji)关系。6.2 图的存储(cn ch)结构及实现假设图G(V,E)有n个顶点(dngdin),则邻接矩阵是一个nn的方阵,定义为:arcij1 若(vi, vj)E(或E)0 其它第47页/共135页第四十八页,共135页。无向图的邻接矩阵的特点?无向(w xin)图的邻接矩阵6.2 图的存储结构(jigu)及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2
25、 V3 V4V1V2V3V4主对角线为 0 且一定(ydng)是对称矩阵。第48页/共135页第四十九页,共135页。如何求顶点i的度?无向(w xin)图的邻接矩阵6.2 图的存储结构(jigu)及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4邻接矩阵的第i行(或第i列)非零元素(yun s)的个数。第49页/共135页第五十页,共135页。如何判断顶点 i 和 j 之间是否存在边?无向(w xin)图的邻接矩阵6.2 图的存储结构(jigu)及实现V1V3V4V2V1 V
26、2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4测试邻接矩阵中相应位置(wi zhi)的元素arcij是否为1。第50页/共135页第五十一页,共135页。如何求顶点 i 的所有邻接点?无向(w xin)图的邻接矩阵6.2 图的存储结构(jigu)及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4将数组中第 i 行元素扫描一遍,若arcij为1,则顶点(dngdin) j 为顶点(dngd
27、in) i 的邻接点。第51页/共135页第五十二页,共135页。6.2 图的存储结构(jigu)及实现有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4有向图的邻接矩阵一定不对称吗?不一定(ydng),例如有向完全图。第52页/共135页第五十三页,共135页。6.2 图的存储(cn ch)结构及实现有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V
28、2V3V4如何求顶点 i 的出度?邻接矩阵的第 i 行元素(yun s)之和。第53页/共135页第五十四页,共135页。6.2 图的存储(cn ch)结构及实现有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何求顶点 i 的入度?邻接矩阵的第 i 列元素(yun s)之和。第54页/共135页第五十五页,共135页。6.2 图的存储(cn ch)结构及实现有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0
29、0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何判断从顶点 i 到顶点 j 是否存在边?测试邻接矩阵中相应(xingyng)位置的元素arcij是否为1。第55页/共135页第五十六页,共135页。网图的邻接矩阵6.2 图的存储(cn ch)结构及实现网图的邻接矩阵可定义为: arcij wij 若(vi, vj)E(或E)0 若i=j 其他V1V2V3V42785 0 2 5 0 0 8 7 0 arc=第56页/共135页第五十七页,共135页。邻接矩阵存储(cn ch)无向图的类const int MaxSize=10; template class Mgrap
30、h public: MGraph(T a , int n, int e ); MGraph( ) void DFSTraverse(int v); void BFSTraverse(int v); private: T vertexMaxSize; int arcMaxSizeMaxSize; int vertexNum, arcNum; ;6.2 图的存储(cn ch)结构及实现第57页/共135页第五十八页,共135页。邻接矩阵中图的基本操作构造函数 1.确定图的顶点个数和边的个数;2.2. 输入(shr)顶点信息存储在一维数组vertex中;3.3. 初始化邻接矩阵;4.4. 依次输入(
31、shr)每条边存储在邻接矩阵arc中;5. 4.1 输入(shr)边依附的两个顶点的序号i, j;6. 4.2 将邻接矩阵的第i行第j列的元素值置为1;7. 4.3 将邻接矩阵的第j行第i列的元素值置为1;6.2 图的存储结构(jigu)及实现第58页/共135页第五十九页,共135页。6.2 图的存储结构(jigu)及实现邻接矩阵中图的基本操作构造函数 第59页/共135页第六十页,共135页。邻接矩阵中图的基本操作深度优先(yuxin)遍历template void MGraph:DFSTraverse(int v) coutvertexv; visited v=1; for (j=0;
32、jvertexNum; j+) if (arcvj=1 & visitedj=0) DFSTraverse( j );6.2 图的存储(cn ch)结构及实现第60页/共135页第六十一页,共135页。邻接矩阵中图的基本操作广度(gungd)优先遍历template void MGraph:BFSTraverse(int v) front=rear=-1; /假设(jish)采用顺序队列且不会发生溢出 coutvertexv; visitedv=1; Q+rear=v; while (front!=rear) v=Q+front; for (j=0; jvertexNum; j+) i
33、f (arcvj=1 & visitedj=0 ) coutvertexj; visitedj=1; Q+rear=j; 6.2 图的存储结构(jigu)及实现第61页/共135页第六十二页,共135页。0100011101100001011010110011001000110010011011110第62页/共135页第六十三页,共135页。邻接(ln ji)表邻接表存储的基本思想:对于图的每个顶点(dngdin)vi,将所有邻接于vi的顶点(dngdin)链成一个单链表,称为顶点(dngdin)vi的边表(对于有向图则称为出边表),所有边表的头指针和存储顶点(dngdin)信息的一
34、维数组构成了顶点(dngdin)表。 6.2 图的存储结构(jigu)及实现图的邻接矩阵存储结构的空间复杂度?如果为稀疏图则会出现什么现象? 假设图G有n个顶点e条边,则存储该图需要O(n2) 。第63页/共135页第六十四页,共135页。第64页/共135页第六十五页,共135页。邻接(ln ji)表有两种结点结构:顶点表结点和边表结点。vertexfirstedge adjvex next 顶点(dngdin)表 边 表 vertex:数据域,存放顶点信息。 firstedge:指针域,指向边表中第一个结点。 adjvex:邻接点域,边的终点在顶点表中的下标(xi bio)。next:指针
35、域,指向边表中的下一个结点。 6.2 图的存储结构及实现第65页/共135页第六十六页,共135页。struct ArcNode int adjvex; ArcNode *next;template struct VertexNode T vertex; ArcNode *firstedge;定义(dngy)邻接表的结点 6.2 图的存储结构(jigu)及实现vertexfirstedge adjvex next第66页/共135页第六十七页,共135页。10323101 V1 V2 V3 V40123vertex firstedge6.2 图的存储(cn ch)结构及实现V1V3V4V2无向
36、(w xin)图的邻接表边表中的结点表示什么?每个结点(ji din)对应图中的一条边,邻接表的空间复杂度为O(n+e)。第67页/共135页第六十八页,共135页。10323101 V1 V2 V3 V40123vertex firstedge6.2 图的存储结构(jigu)及实现V1V3V4V2无向(w xin)图的邻接表如何求顶点 i 的度?顶点(dngdin)i的边表中结点的个数。第68页/共135页第六十九页,共135页。如何判断顶点 i 和顶点 j之间是否存在边?测试顶点 i 的边表中是否存在(cnzi)终点为 j 的结点。6.2 图的存储结构(jigu)及实现10323101 V
37、1 V2 V3 V40123vertex firstedgeV1V3V4V2无向(w xin)图的邻接表第69页/共135页第七十页,共135页。6.2 图的存储结构(jigu)及实现有向图的邻接(ln ji)表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求顶点 i 的出度?顶点(dngdin) i 的出边表中结点的个数。第70页/共135页第七十一页,共135页。6.2 图的存储(cn ch)结构及实现有向图的邻接(ln ji)表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求顶点 i 的入度?各顶
38、点(dngdin)的出边表中以顶点(dngdin) i 为终点的结点个数。第71页/共135页第七十二页,共135页。6.2 图的存储结构(jigu)及实现有向图的邻接(ln ji)表V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求顶点 i 的所有邻接点?遍历顶点(dngdin) i 的边表,该边表中的所有终点都是顶点(dngdin) i 的邻接点。第72页/共135页第七十三页,共135页。6.2 图的存储(cn ch)结构及实现网图的邻接(ln ji)表V1V2V3V427852 1 V1 V2 V3 V40123vertex firstedg
39、e5 28 37 0第73页/共135页第七十四页,共135页。邻接(ln ji)表存储有向图的类const int MaxSize=10; /图的最大顶点(dngdin)数template class ALGraph public: ALGraph(T a , int n, int e); ALGraph; void DFSTraverse(int v); void BFSTraverse(int v); private: VertexNode adjlistMaxSize; int vertexNum, arcNum; ;6.2 图的存储(cn ch)结构及实现第74页/共135页第七十五
40、页,共135页。邻接(ln ji)表中图的基本操作构造函数 1. 确定图的顶点个数和边的个数;2. 输入顶点信息,初始化该顶点的边表;3. 依次输入边的信息并存储在边表中; 3.1 输入边所依附的两个顶点的序号i和j; 3.2 生成邻接(ln ji)点序号为j的边表结点s; 3.3 将结点s插入到第i个边表的头部;6.2 图的存储(cn ch)结构及实现第75页/共135页第七十六页,共135页。template ALGraph:ALGraph(T a , int n, int e) vertexNum=n; arcNum=e; for (i=0; ivertexNum; i+) /输入(sh
41、r)顶点信息,初始化边表 adjlisti.vertex=ai; adjlisti.firstedge=NULL; 6.2 图的存储结构(jigu)及实现邻接(ln ji)表中图的基本操作构造函数 第76页/共135页第七十七页,共135页。s for (k=0; kij; s=new ArcNode; s-adjvex=j; s-next=adjlisti.firstedge; adjlisti.firstedge=s; 6.2 图的存储(cn ch)结构及实现12 V1 V2 V3 V40123第77页/共135页第七十八页,共135页。邻接(ln ji)表中图的基本操作深度优先遍历tem
42、plate void ALGraph:DFSTraverse(int v) coutadjvex; if (visitedj=0) DFSTraverse(j); p=p-next; 6.2 图的存储结构(jigu)及实现第78页/共135页第七十九页,共135页。邻接表中图的基本操作广度优先(yuxin)遍历template void ALGraph:BFSTraverse(int v) front=rear=-1; coutadjvex; if (visitedj=0) coutnext; 6.2 图的存储结构(jigu)及实现第79页/共135页第八十页,共135页。邻接表6.2 图的存
43、储结构(jigu)及实现逆邻接表V1V2V3V412 3 0v1v2v3v401231 3 0 2 v1v2v3v4012303 第80页/共135页第八十一页,共135页。图的存储(cn ch)结构的比较邻接矩阵和邻接表O(n2)O(n+e)O(n2)O(n+e)空间性能 时间性能 适用范围 唯一性邻接矩阵邻接表稠密图稀疏图唯一不唯一6.2 图的存储(cn ch)结构及实现第81页/共135页第八十二页,共135页。生成树的代价:设G=(V,E)是一个(y )无向连通网,生成树上各边的权值之和称为该生成树的代价。 最小生成树:在图G所有生成树中,代价(diji)最小的生成树称为最小生成树。
44、应用举例(j l)最小生成树最小生成树最小生成树的概念可以应用到许多实际问题中。例:在n个城市之间建造通信网络,至少要架设n-1条通信线路,而每两个城市之间架设通信线路的造价是不一样的,那么如何设计才能使得总造价最小? 第82页/共135页第八十三页,共135页。MST性质(xngzh)假设G=(V, E)是一个(y )无向连通网,U是顶点集V的一个(y )非空子集。若(u, v)是一条具有最小权值的边,其中uU,vVU,则必存在一棵包含边(u, v)的最小生成树。应用(yngyng)举例最小生成树顶点集UVUuvvu顶点集T1T2第83页/共135页第八十四页,共135页。基本思想:设G=(
45、V, E)是具有n个顶点的连通网,T=(U, TE)是G的最小生成树, T的初始状态为U=u0(u0V),TE= ,重复执行下述操作:在所有uU,vV-U的边中找一条代价最小的边(u, v)并入(bn r)集合TE,同时v并入(bn r)U,直至U=V。关键:是如何(rh)找到连接U和V-U的最短边。 普里姆(Prim)算法(sun f) 应用举例最小生成树利用MST性质,可以用下述方法构造候选最短边集:对应V-U中的每个顶点,保留从该顶点到U中的各顶点的最短边。 第84页/共135页第八十五页,共135页。第85页/共135页第八十六页,共135页。例16543265135664251311
46、63141643142116432142516543214253第86页/共135页第八十七页,共135页。假设开始顶点(dngdin)就选为顶点(dngdin)1,故首先有U=1,W=2,3,4,5,6 (a )无向网 (b) u=1 w=2,3,4,5,6 6 4 1 2 4 6 3 6 2 1 3 5 7 6 5 5 5 1 2 3 4 5 6 6 5 1 i123456closesti111111lowcosti 0615 06246053207545705135065160closest用于存放(cnfng)顶点序号lowest存放(cnfng)权值(该顶点到已选所有顶点的最小边权值
47、)第87页/共135页第八十八页,共135页。 3 1 2 4 6 5 6 1 4 5 5 5 3 1 2 4 6 5 6 4 2 1 5 5 (c ) u=1,3 w=2,4,5,6 (d) u=1,3,6 w=2,4,5 i123456closesti131133lowcosti 0505 54 i123456closesti131633lowcosti 0502 50 第88页/共135页第八十九页,共135页。 3 1 2 4 6 5 6 4 2 1 5 5 (e) u=1,3,6,4 w=2,5 (f) u=1,3,6,4,2 w=5 1 2 4 6 3 5 6 4 2 1 5 3
48、(g) u=1,3,6,4,2,5 w= 5 4 2 1 3 1 2 4 6 3 5 6 图 8-20 prim 方法构造最小生成树的过程 i123456closesti131633lowcosti 050050i123456closesti131623lowcosti 000030 i123456closesti131623lowcosti 000000 第89页/共135页第九十页,共135页。#define INFINITE 9999#define MAXN 100void prim(int costMAXN,int n,int v) int lowcostMAXN,min,closes
49、tMAXN,i,j,k; for(i=1;i=n;i+) lowcosti=costvi; closesti=v; for(i=1;in;i+) min=INFINITE; for(j=1;j=n;j+) if(lowcostj!=0&lowcostjmin) min=lowcostj; k=j; 第90页/共135页第九十一页,共135页。printf(“%d%d%d”,closestk,k,min);lowcostk=0;for(j=1;j=n;j+) if(costkj!=0)&(costkjlowcostj) lowcostj=costkj; closestj=k;分析
50、(fnx):时间复杂度为O(n2)第91页/共135页第九十二页,共135页。克鲁斯卡尔(Kruskal)算法(sun f) 基本思想:设无向连通网为G(V, E),令G的最小生成树为T(U, TE),其初态为UV,TE ,然后,按照边的权值由小到大的顺序,考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量,则将此边作为最小生成树的边加入到T中,同时把两个连通分量连接为一个(y )连通分量;若被考察边的两个顶点属于同一个(y )连通分量,则舍去此边,以免造成回路,如此下去,当T中的连通分量个数为1时,此连通分量便为G的一棵最小生成树。 应用举例(j l)最小生成树第92
51、页/共135页第九十三页,共135页。251234192646381725ABEDCF应用(yngyng)举例最小生成树ABEDCF连通(lintng)分量A, B, C, D, E, F第93页/共135页第九十四页,共135页。251234192646381725ABEDCF应用(yngyng)举例最小生成树ABEDCF连通(lintng)分量A, B, C, D, E, F12连通(lintng)分量A, B, E, C, D, F第94页/共135页第九十五页,共135页。251234192646381725ABEDCF应用举例(j l)最小生成树ABEDCF连通(lintng)分量A
52、, B, E, C, D, F12连通(lintng)分量A, F, B, E, C, D19第95页/共135页第九十六页,共135页。251234192646381725ABEDCF应用(yngyng)举例最小生成树ABEDCF连通(lintng)分量A, F, B, E, C, D12连通(lintng)分量A, F, B, E, C, D1917第96页/共135页第九十七页,共135页。251234192646381725ABEDCF应用(yngyng)举例最小生成树ABEDCF连通(lintng)分量A, F, B, E, C, D12连通(lintng)分量A, F, C, D,
53、 B, E191725第97页/共135页第九十八页,共135页。251234192646381725ABEDCF应用举例(j l)最小生成树ABEDCF连通(lintng)分量A, F, C, D, B, E12连通(lintng)分量A, F, C, D, B, E19172526第98页/共135页第九十九页,共135页。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 在E中标记边(u,v
54、),使得(u,v)不参加后续(hux)最短边的选取;应用举例(j l)最小生成树Kruskal算法(sun f)伪代码第99页/共135页第一百页,共135页。第100页/共135页第一百零一页,共135页。在非网图中,最短路径是指两顶点(dngdin)之间经历的边数最少的路径。 应用举例(j l)最短路径最短路径(ljng) BAEDCAE:1ADE:2 ADCE:3ABCE:3第101页/共135页第一百零二页,共135页。应用(yngyng)举例最短路径最短路径(ljng) 在网图中,最短路径是指两顶点(dngdin)之间经历的边上权值之和最短的路径。 BAEDC105030101002
55、060AE:100ADE:90 ADCE:60 ABCE:70第102页/共135页第一百零三页,共135页。问题描述:给定(i dn)带权有向图G(V, E)和源点vV,求从v到G中其余各顶点的最短路径。 单源点最短路径(ljng)问题 应用举例(j l)最短路径应用实例计算机网络传输的问题:怎样找到一种最经济的方式,从一台计算机向网上所有其它计算机发送一条消息。迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的次序产生最短路径的算法Dijkstra算法。第103页/共135页第一百零四页,共135页。基本思想(sxing):设置一个集合S存放已经找到最短路径的顶点,S的初始状态只包含
56、源点v,对viV-S,假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, , vk,就将vk加入集合S中,并将路径v, , vk , vi与原来的假设相比较,取路径长度较小者为最短路径。重复上述过程,直到集合V中全部顶点加入到集合S中。Dijkstra算法(sun f)应用(yngyng)举例最短路径第104页/共135页第一百零五页,共135页。 集 合 V -S集合 SvkvviDijkstra算法的基本(jbn)思想应用举例(j l)最短路径第105页/共135页第一百零六页,共135页。ABAEDC105030101002060S=AAB:(A, B)10AC:(A, C
57、)AD: (A, D)30AE: (A, E)100应用举例(j l)最短路径Dijkstra算法(sun f)第106页/共135页第一百零七页,共135页。ABAEDC105030101002060S=A, BAB:(A, B)10AC:(A, B, C)60AD: (A, D)30AE: (A, E)100应用举例(j l)最短路径BDijkstra算法(sun f)第107页/共135页第一百零八页,共135页。ABAEDC105030101002060S=A, B, DAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, E)90应用举例(j
58、 l)最短路径BDDijkstra算法(sun f)第108页/共135页第一百零九页,共135页。ABAEDC105030101002060S=A, B, D, CAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, C, E)60应用举例(j l)最短路径BDCDijkstra算法(sun f)第109页/共135页第一百一十页,共135页。ABAEDC105030101002060Dijkstra算法(sun f)S=A, B, D, C, EAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, C, E
59、)60应用(yngyng)举例最短路径BDCE第110页/共135页第一百一十一页,共135页。第111页/共135页第一百一十二页,共135页。1715650710201820382301254637812第112页/共135页第一百一十三页,共135页。AOV网:在一个表示工程的有向图中,用顶点表示活动(hu dng),用弧表示活动(hu dng)之间的优先关系,称这样的有向图为顶点表示活动(hu dng)的网,简称AOV网。 应用举例(j l)拓扑排序AOV网什么是工程?工程有什么共性?AOV网中出现回路意味着什么?第113页/共135页第一百一十四页,共135页。AOV网:在一个表示工
60、程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系(gun x),称这样的有向图为顶点表示活动的网,简称AOV网。 应用举例(j l)拓扑排序AOV网2.AOV网中不能出现回路 。AOV网特点:1.AOV网中的弧表示活动之间存在的某种制约关系。 什么是工程?工程有什么共性?第114页/共135页第一百一十五页,共135页。编号编号课程名称课程名称先修课先修课C1高等数学高等数学无无C2计算机导论计算机导论无无C3离散数学离散数学C1C4程序设计程序设计C1, C2C5数据结构数据结构C3,C4C6计算机原理计算机原理C2,C4C7数据库原理数据库原理C4,C5,C6应用(yngyng)举例拓扑排序C1C2C3C4C6
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026-2027学年上学期单元测试八年级语文检测卷电子版
- 2026-2027学年上学期单元测试二年级科学模拟卷及答案
- 健身音响系统:从背景音乐到沉浸式训练体验:健身音响系统市场的产品升级与增长机遇
- 2025CFA一级财务报表分析复习重点题及答案
- 零售业销售经理工作绩效考核表
- 能源设备技术支持专家问题解决能力绩效衡量表
- 确认完成2026年设备验收流程通知函(3篇)
- 山地徒步恶劣天气紧急疏散方案
- 餐饮行业外卖订单处理指南
- 事业单位计算机岗面试2026高频考题强化训练试卷及答案
- 2026上海新闻出版职业技术学校下半年招聘工作人员6人考试模拟试题及答案解析
- 家庭保洁作业安全方案
- 2026年人民调解员业务考试题库
- IEC 62351-92023 电力系统管理和相关信息交换.数据和通信安全.第9部分电力系统设备的网络安全密钥管理标准立项发展报告
- 2026年湖南高职单招职业技能测试考试题库(附含答案)
- 水利水电工程单元工程施工质量检验表与验收表(SLT631.5-2025)
- 做账实操-民宿账务处理分录SOP
- 泌尿系统疾病试题及答案
- HJ 2301-2017火电厂污染防治可行技术指南
- 开心国学院词班填词知识第1讲:十六字令填写方法
- T/CPUMT 002-2022基于倾斜航空摄影的实景三维模型构建技术规范
评论
0/150
提交评论