数数据结构图.pptx

《数数据结构图.pptx》由会员分享，可在线阅读，更多相关《数数据结构图.pptx（135页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？哥尼斯堡七桥问题 第1页/共135页CADB七桥问题的图模型哥尼斯堡七桥问题 欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。第2页/共135页图的定义图的定义6.1 6.1 图的逻辑结构图的逻辑结构图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；

2、在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。第3页/共135页6.1 6.1 图的逻辑结构图的逻辑结构如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为。如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。V1V2V3V4V5V1V2V3V4第4页/共135页6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简

3、单图 非简单图 简单图V1V2V3V4V5v 数据结构中讨论的都是简单图。第5页/共135页6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。V1V2V3V4V5V1的邻接点：V2、V4V2的邻接点：V1、V3、V5第6页/共135页6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧依附于顶点vi和顶点vj。V

4、1V2V3V4V1的邻接点：V2、V3V3的邻接点：V4第7页/共135页在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比第8页/共135页在线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比第9页/共135页无向完全图：在无向图中，如果任意

5、两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。图的基本术语 V1V2V3V1V2V3V46.1 6.1 图的逻辑结构图的逻辑结构第10页/共135页含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？6.1 6.1 图的逻辑结构图的逻辑结构含有n个顶点的无向完全图有n(n-1)/2条边。含有n个顶点的有向完全图有n(n-1)条边。V1V2V3V1V2V3V4第11页/共135页稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点

6、的边数，通常记为TD(v)。6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。第12页/共135页V1V2V3V4V56.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？=niievTD12)(第13页/共135页V1V2V3V46.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？

7、与边数之和的关系？evODvIDiiii=11)()(nn第14页/共135页权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 V1V2V3V42785第15页/共135页路径：在无向图G=(V,E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,vim=vq)，其中，(vij-1,vij)E（1jm）。若G是有向图，则路径也是有方向的，顶点序列满足E。6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 V1V2V3V4V5v一般情况下，图中的路径不惟一。V1 到V4的路径：V1 V4 V1 V

8、2 V3 V4 V1 V2 V5V3 V4第16页/共135页路径长度：6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 非带权图路径上边的个数带权图路径上各边的权之和V1V2V3V4V5V1 V4：长度为1V1 V2 V3 V4：长度为3V1 V2 V5V3 V4：长度为4第17页/共135页路径长度：6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 非带权图路径上边的个数带权图路径上各边的权之和V1 V4：长度为8V1 V2 V3 V4：长度为7V1 V2 V5V3 V4：长度为15V1V2V3V4V5256328第18页/共135页回路（环）：第一个顶点和最后一个顶点相同的路径。

9、简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 V1V2V3V4V5V1V2V3V4第19页/共135页子图：若图G=（V，E），G=（V，E），如果VV 且E E，则称图G是G的子图。6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 V1V2V3V4V5V1V2V3V4V5V1V3V4第20页/共135页连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图

10、的极大连通子图称为连通分量。6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 如何求得一个非连通图的连通分量?1.含有极大顶点数；2.依附于这些顶点的所有边。第21页/共135页连通分量1 6.1 6.1 图的逻辑结构图的逻辑结构V1V2V3V4V5V6V7V1V2V4V5V3V6V7连通分量2图的基本术语 v连通分量是对无向图的一种划分。第22页/共135页强连通图：在有向图中，对图中任意一对顶点vi和vj(ij)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 如

11、何求得一个非连通图的连通分量?第23页/共135页6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 V1V2V3V4强连通分量1 强连通分量2V1V3V4V2第24页/共135页生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。如何理解极小连通子图?6.1 6.1 图的逻辑结构图的逻辑结构图的基本术语 多构成回路少不连通含有n-1条边第25页/共135页V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成

12、森林6.1 6.1 图的逻辑结构图的逻辑结构第26页/共135页图的抽象数据类型定义图的抽象数据类型定义 ADT GraphData 顶点的有穷非空集合和边的集合Operation InitGraph 前置条件：图不存在 输入：无 功能：图的初始化 输出：无 后置条件：构造一个空的图6.1 6.1 图的逻辑结构图的逻辑结构第27页/共135页 DFSTraverse 前置条件：图已存在 输入：遍历的起始顶点v 功能：从顶点v出发深度优先遍历图 输出：图中顶点的一个线性排列 后置条件：图保持不变 BFSTraverse 前置条件：图已存在 输入：遍历的起始顶点v 功能：从顶点v出发广度优先遍历图

13、 输出：图中顶点的一个线性排列 后置条件：图保持不变6.1 6.1 图的逻辑结构图的逻辑结构第28页/共135页DestroyGraph 前置条件：图已存在 输入：无 功能：销毁图 输出：无 后置条件：释放图所占用的存储空间GetVex 前置条件：图已存在 输入：顶点v 功能：在图中查找顶点v的数据信息 输出：顶点v的数据信息 后置条件：图保持不变endADT6.1 6.1 图的逻辑结构图的逻辑结构第29页/共135页图的遍历操作图的遍历操作图的遍历是在从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。6.1 6.1 图的逻辑结构图的逻辑结构抽象操作，可以是对结点进行的各种处理，这里简化

14、为输出结点的数据。第30页/共135页图的遍历操作要解决的关键问题 在图中，如何选取遍历的起始顶点？6.1 6.1 图的逻辑结构图的逻辑结构n在线性表中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的；n在树中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；n在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。解决方案：从编号小的顶点开始。第31页/共135页 从某个起点始可能到达不了所有其它顶点，怎么办？6.1 6.1 图的逻辑结构图的逻辑结构图的

15、遍历操作要解决的关键问题解决方案：多次调用从某顶点出发遍历图的算法。v下面仅讨论从某顶点出发遍历图的算法。第32页/共135页 因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环。在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？6.1 6.1 图的逻辑结构图的逻辑结构图的遍历操作要解决的关键问题解决方案：附设访问标志数组visitedn。解决方案：深度优先遍历和广度优先遍历。第33页/共135页约翰霍普克洛夫特1939年生于西雅图。1961年进入斯坦福大学研究生院深造，1962年获硕士学位，1964年获博士学位。毕业后

16、先后在普林斯顿大学、斯坦福大学等著名学府工作，也曾任职于一些科学研究机构如 NSF（美国科学基金会）和 NRC（美国国家研究院）。罗伯特陶尔扬1948年4月30日生于加利福尼亚州。1969年本科毕业，进入斯坦福大学研究生院，1972年获得博士学位。1986年图灵奖获得者6.1 6.1 图的逻辑结构图的逻辑结构第34页/共135页1.深度优先遍历 基本思想：访问顶点v；从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。6.1 6.1 图的逻辑结构图的逻辑结构第35页/共135页深一层递归递归返回深度优先遍历序列?入栈序列?

17、出栈序列?6.1 6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8 V1遍历序列：V1V2 V2V4 V4V5 V5第36页/共135页深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.1 6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8 V1遍历序列：V1V2 V2V4 V4V5V8 V8第37页/共135页深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.1 6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8 V1遍历序列：V1V2 V2V4 V4V5V8第38页/共135页深一层递归递归返回深度优先遍历序列?入栈序列?出栈

18、序列?6.1 6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8 V1遍历序列：V1 V7V2V4V5V8V3 V3V6 V6V7第39页/共135页2.广度优先遍历 基本思想：访问顶点v；依次访问v的各个未被访问的邻接点v1,v2,vk；分别从v1，v2，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。6.1 6.1 图的逻辑结构图的逻辑结构第40页/共135页广度优先遍历序列?入队序列?出队序列?6.1 6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列

19、：V1V1第41页/共135页广度优先遍历序列?入队序列?出队序列?6.1 6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V2V3V3第42页/共135页广度优先遍历序列?入队序列?出队序列?6.1 6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V3V4V4V5V5第43页/共135页广度优先遍历序列?入队序列?出队序列?6.1 6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V4V5V5V6V6V7V7第44页/共135页广度优先遍历序列?入队序列?出队序列?6.1 6.1

20、图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V8第45页/共135页6.2 6.2 图的存储结构及实现图的存储结构及实现是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。第46页/共135页邻接矩阵（数组表示法）邻接矩阵（数组表示法）基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间

21、的邻接关系。6.2 6.2 图的存储结构及实现图的存储结构及实现假设图G(V，E)有n个顶点，则邻接矩阵是一个nn的方阵，定义为：arcij1 若(vi,vj)E（或E）0 其它第47页/共135页无向图的邻接矩阵的特点？无向图的邻接矩阵6.2 6.2 图的存储结构及实现图的存储结构及实现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主对角线为 0 且一定是对称矩阵。第48页/共135页如何求顶点i的度？无向图的邻接矩阵6.2 6.2 图的存储结构及实现图的存储结构及实现V1V3

22、V4V2V1 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列）非零元素的个数。第49页/共135页如何判断顶点 i 和 j 之间是否存在边？无向图的邻接矩阵6.2 6.2 图的存储结构及实现图的存储结构及实现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测试邻接矩阵中相应位置的元素arcij是否为1。第50页/共135页如何求顶点 i 的所有邻接点？无向图的邻接

23、矩阵6.2 6.2 图的存储结构及实现图的存储结构及实现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，则顶点 j 为顶点 i 的邻接点。第51页/共135页6.2 6.2 图的存储结构及实现图的存储结构及实现有向图的邻接矩阵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有向图的邻接矩阵一定不对称吗？不一定，例如有向完

24、全图。第52页/共135页6.2 6.2 图的存储结构及实现图的存储结构及实现有向图的邻接矩阵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 行元素之和。第53页/共135页6.2 6.2 图的存储结构及实现图的存储结构及实现有向图的邻接矩阵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

25、 列元素之和。第54页/共135页6.2 6.2 图的存储结构及实现图的存储结构及实现有向图的邻接矩阵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 到顶点 j 是否存在边？测试邻接矩阵中相应位置的元素arcij是否为1。第55页/共135页网图的邻接矩阵6.2 6.2 图的存储结构及实现图的存储结构及实现网图的邻接矩阵可定义为：arcij wij 若(vi,vj)E（或E）0 若i=j 其他V1V2V3V42785 0 2 5 0 0 8 7 0 arc=第5

26、6页/共135页邻接矩阵存储无向图的类const int MaxSize=10;template class Mgraph 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 6.2 图的存储结构及实现图的存储结构及实现第57页/共135页邻接矩阵中图的基本操作构造函数 1.确定图的顶点个数和边的个数；2.输入顶点信息存储在一维数组v

27、ertex中；3.初始化邻接矩阵；4.依次输入每条边存储在邻接矩阵arc中；4.1 输入边依附的两个顶点的序号i,j；4.2 将邻接矩阵的第i行第j列的元素值置为1；4.3 将邻接矩阵的第j行第i列的元素值置为1；6.2 6.2 图的存储结构及实现图的存储结构及实现第58页/共135页template MGraph:MGraph(T a,int n,int e)vertexNum=n;arcNum=e;for(i=0;ivertexNum;i+)vertexi=ai;for(i=0;ivertexNum;i+)/初始化邻接矩阵 for(j=0;jvertexNum;j+)arcij=0;for

28、(k=0;kij;/边依附的两个顶点的序号 arcij=1;arcji=1;/置有边标志 6.2 6.2 图的存储结构及实现图的存储结构及实现邻接矩阵中图的基本操作构造函数 第59页/共135页邻接矩阵中图的基本操作深度优先遍历template void MGraph:DFSTraverse(int v)coutvertexv;visited v=1;for(j=0;jvertexNum;j+)if(arcvj=1&visitedj=0)DFSTraverse(j);6.2 6.2 图的存储结构及实现图的存储结构及实现第60页/共135页邻接矩阵中图的基本操作广度优先遍历template vo

29、id MGraph:BFSTraverse(int v)front=rear=-1;/假设采用顺序队列且不会发生溢出 coutvertexv;visitedv=1;Q+rear=v;while(front!=rear)v=Q+front;for(j=0;jvertexNum;j+)if(arcvj=1&visitedj=0)coutvertexj;visitedj=1;Q+rear=j;6.2 6.2 图的存储结构及实现图的存储结构及实现第61页/共135页已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。第62页/共135页邻接表邻

30、接表邻接表存储的基本思想：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。6.2 6.2 图的存储结构及实现图的存储结构及实现图的邻接矩阵存储结构的空间复杂度？如果为稀疏图则会出现什么现象？假设图G有n个顶点e条边，则存储该图需要O(n2)。第63页/共135页图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法，它包括两部分：一部分是单链表，用来存放边的信息；另一部分是数组，主要用来存放顶点本身的数据信息。第64页/共135页邻接表有两种结点结构：顶点表结点和边表结点。ver

31、texfirstedge adjvex next 顶点表 边 表 vertex：数据域，存放顶点信息。firstedge：指针域，指向边表中第一个结点。adjvex：邻接点域，边的终点在顶点表中的下标。next：指针域，指向边表中的下一个结点。6.2 6.2 图的存储结构及实现图的存储结构及实现第65页/共135页struct ArcNode int adjvex;ArcNode*next;template struct VertexNode T vertex;ArcNode*firstedge;定义邻接表的结点 6.2 6.2 图的存储结构及实现图的存储结构及实现vertexfirstedg

32、e adjvex next第66页/共135页10323101 V1 V2 V3 V40123vertex firstedge6.2 6.2 图的存储结构及实现图的存储结构及实现V1V3V4V2无向图的邻接表边表中的结点表示什么？每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。第67页/共135页10323101 V1 V2 V3 V40123vertex firstedge6.2 6.2 图的存储结构及实现图的存储结构及实现V1V3V4V2无向图的邻接表如何求顶点 i 的度？顶点i的边表中结点的个数。第68页/共135页如何判断顶点 i 和顶点 j之间是否存在边?测试顶点 i 的

33、边表中是否存在终点为 j 的结点。6.2 6.2 图的存储结构及实现图的存储结构及实现10323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2无向图的邻接表第69页/共135页6.2 6.2 图的存储结构及实现图的存储结构及实现有向图的邻接表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求顶点 i 的出度？顶点 i 的出边表中结点的个数。第70页/共135页6.2 6.2 图的存储结构及实现图的存储结构及实现有向图的邻接表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge

34、如何求顶点 i 的入度？各顶点的出边表中以顶点 i 为终点的结点个数。第71页/共135页6.2 6.2 图的存储结构及实现图的存储结构及实现有向图的邻接表V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求顶点 i 的所有邻接点？遍历顶点 i 的边表，该边表中的所有终点都是顶点 i 的邻接点。第72页/共135页6.2 6.2 图的存储结构及实现图的存储结构及实现网图的邻接表V1V2V3V427852 1 V1 V2 V3 V40123vertex firstedge5 28 37 0第73页/共135页邻接表存储有向图的类const int Max

35、Size=10;/图的最大顶点数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 6.2 图的存储结构及实现图的存储结构及实现第74页/共135页邻接表中图的基本操作构造函数 1.确定图的顶点个数和边的个数；2.输入顶点信息，初始化该顶点的边表；3.依次输入边的信息并存储在边表中；3.1 输入边所依附的两个顶

36、点的序号i和j；3.2 生成邻接点序号为j的边表结点s；3.3 将结点s插入到第i个边表的头部；6.2 6.2 图的存储结构及实现图的存储结构及实现第75页/共135页template ALGraph:ALGraph(T a,int n,int e)vertexNum=n;arcNum=e;for(i=0;ivertexNum;i+)/输入顶点信息，初始化边表 adjlisti.vertex=ai;adjlisti.firstedge=NULL;6.2 6.2 图的存储结构及实现图的存储结构及实现邻接表中图的基本操作构造函数 第76页/共135页s for(k=0;kij;s=new ArcN

37、ode;s-adjvex=j;s-next=adjlisti.firstedge;adjlisti.firstedge=s;6.2 6.2 图的存储结构及实现图的存储结构及实现12 V1 V2 V3 V40123第77页/共135页邻接表中图的基本操作深度优先遍历template void ALGraph:DFSTraverse(int v)coutadjvex;if(visitedj=0)DFSTraverse(j);p=p-next;6.2 6.2 图的存储结构及实现图的存储结构及实现第78页/共135页邻接表中图的基本操作广度优先遍历template void ALGraph:BFSTr

38、averse(int v)front=rear=-1;coutadjvex;if(visitedj=0)coutnext;6.2 6.2 图的存储结构及实现图的存储结构及实现第79页/共135页邻接表6.2 6.2 图的存储结构及实现图的存储结构及实现逆邻接表V1V2V3V412 3 0v1v2v3v401231 3 0 2 v1v2v3v4012303 第80页/共135页图的存储结构的比较图的存储结构的比较邻接矩阵和邻接表邻接矩阵和邻接表O（n2）O（n+e）O（n2）O（n+e）空间性能 时间性能 适用范围 唯一性邻接矩阵邻接表稠密图稀疏图唯一不唯一6.2 6.2 图的存储结构及实现图的

39、存储结构及实现第81页/共135页生成树的代价：设G=（V，E）是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。应用举例应用举例最小生成树最小生成树最小生成树最小生成树最小生成树的概念可以应用到许多实际问题中。例：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？第82页/共135页MST性质假设G=(V,E)是一个无向连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中uU，vVU，则必存在一棵包含边(u,v)

40、的最小生成树。应用举例应用举例最小生成树最小生成树顶点集UVUuvvu顶点集T1T2第83页/共135页基本思想：设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是G的最小生成树，T的初始状态为U=u0（u0V），TE=，重复执行下述操作：在所有uU，vV-U的边中找一条代价最小的边(u,v)并入集合TE，同时v并入U，直至U=V。关键:是如何找到连接U和V-U的最短边。普里姆（Prim）算法 应用举例应用举例最小生成树最小生成树利用MST性质，可以用下述方法构造候选最短边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。第84页/共135页1、Prim算法求解方法求解方

41、法 Prim算法通常要指定一个起点，其求解思想非常简单：首先将所指定的起点作为已选顶点已选顶点，然后反复在满足如下条件的边中选择一条最小边，直到所有顶点成为已选顶点为止（选择n-1条边）：一端已选，另一端未选。一端已选，另一端未选。第85页/共135页例1654326513566425131163141643142116432142516543214253第86页/共135页假设开始顶点就选为顶点1，故首先有U=1，W=2，3，4，5，6i123456closesti111111lowcosti 0615 closest用于存放顶点序号lowest存放权值(该顶点到已选所有顶点的最小边权值)第

42、87页/共135页i123456closesti131133lowcosti 0505 54 i123456closesti131633lowcosti 0502 50 第88页/共135页i123456closesti131633lowcosti 050050i123456closesti131623lowcosti 000030 i123456closesti131623lowcosti 000000 第89页/共135页#define INFINITE 9999#define MAXN 100void prim(int costMAXN,int n,int v)int lowcostMA

43、XN,min,closestMAXN,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页printf(“%d%d%d”,closestk,k,min);lowcostk=0;for(j=1;j=n;j+)if(costkj!=0)&(costkjlowcostj)lowcostj=costkj;closestj=k;分析:时间复杂度为O(n2)第91页/共13

44、5页克鲁斯卡尔（Kruskal）算法 基本思想：设无向连通网为G(V,E)，令G的最小生成树为T(U,TE)，其初态为UV，TE，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。应用举例应用举例最小生成树最小生成树第92页/共135页251234192646381725ABEDCF应用举例应用举例最小生成树最小生成树ABE

45、DCF连通分量A,B,C,D,E,F第93页/共135页251234192646381725ABEDCF应用举例应用举例最小生成树最小生成树ABEDCF连通分量A,B,C,D,E,F12连通分量A,B,E,C,D,F第94页/共135页251234192646381725ABEDCF应用举例应用举例最小生成树最小生成树ABEDCF连通分量A,B,E,C,D,F12连通分量A,F,B,E,C,D19第95页/共135页251234192646381725ABEDCF应用举例应用举例最小生成树最小生成树ABEDCF连通分量A,F,B,E,C,D12连通分量A,F,B,E,C,D1917第96页/共

46、135页251234192646381725ABEDCF应用举例应用举例最小生成树最小生成树ABEDCF连通分量A,F,B,E,C,D12连通分量A,F,C,D,B,E191725第97页/共135页251234192646381725ABEDCF应用举例应用举例最小生成树最小生成树ABEDCF连通分量A,F,C,D,B,E12连通分量A,F,C,D,B,E19172526第98页/共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 将这

47、两个连通分量合为一个；2.3 在E中标记边(u，v)，使得(u，v)不参加后续最短边的选取；应用举例应用举例最小生成树最小生成树Kruskal算法伪代码第99页/共135页请对下图的无向带权图：1)写出它的邻接矩阵，并按普里姆算法求其最小生成树；2)按克鲁斯卡尔算法求其最小生成树。第100页/共135页在非网图中，最短路径是指两顶点之间经历的边数最少的路径。应用举例应用举例最短路径最短路径最短路径 BAEDCAE：1ADE：2 ADCE：3ABCE：3第101页/共135页应用举例应用举例最短路径最短路径最短路径 在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。BAEDC1050

48、30101002060AE：100ADE：90 ADCE：60 ABCE：70第102页/共135页问题描述：给定带权有向图G(V,E)和源点vV，求从v到G中其余各顶点的最短路径。单源点最短路径问题 应用举例应用举例最短路径最短路径应用实例计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法Dijkstra算法。第103页/共135页基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对viV-S，假设从源点v到vi的有向边为最短路径。以后每求得一

49、条最短路径v,vk，就将vk加入集合S中，并将路径v,vk,vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。Dijkstra算法应用举例应用举例最短路径最短路径第104页/共135页 集 合 V-S集合 SvkvviDijkstra算法的基本思想应用举例应用举例最短路径最短路径第105页/共135页ABAEDC105030101002060S=AAB:(A,B)10AC:(A,C)AD:(A,D)30AE:(A,E)100应用举例应用举例最短路径最短路径Dijkstra算法第106页/共135页ABAEDC105030101002060S=

50、A,BAB:(A,B)10AC:(A,B,C)60AD:(A,D)30AE:(A,E)100应用举例应用举例最短路径最短路径BDijkstra算法第107页/共135页ABAEDC105030101002060S=A,B,DAB:(A,B)10AC:(A,D,C)50AD:(A,D)30AE:(A,D,E)90应用举例应用举例最短路径最短路径BDDijkstra算法第108页/共135页ABAEDC105030101002060S=A,B,D,CAB:(A,B)10AC:(A,D,C)50AD:(A,D)30AE:(A,D,C,E)60应用举例应用举例最短路径最短路径BDCDijkstra算法