数据结构王红梅图PPT课件

1、欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他一生共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。 欧拉对著名的哥尼斯堡七桥问题的解答开创了图论的研究。图论欧拉第1页/共167页能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？哥尼斯堡七桥问题 第2

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

3、 图的逻辑结构如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为。 如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。V0V1V2V3V4V0V1V2V3第5页/共167页6.1 图的逻辑结构图的基本术语 简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。非简单图 非简单图 简单图v 数据结构中讨论的都是简单图。V0V1V2V3V4V0V1V2V3V4V0V1V2V3V4第6页/共167页6.1 图的逻辑结构图的基本术语 邻接、依附无

4、向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。V0的邻接点： V1 、V3V1的邻接点： V0 、V2 、V4V0V1V2V3V4第7页/共167页6.1 图的逻辑结构图的基本术语 邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧依附于顶点vi和顶点vj 。 V0V1V2V3V0的邻接点： V1 、V2V2的邻接点： V3第8页/共167页在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在图结构

5、中，任意两个顶点之间都可能有关系。 FECBAD线性结构ABCDEF树结构不同结构中逻辑关系的对比V0V1V2V3V4图结构第9页/共167页在线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。 FECBAD线性结构ABCDEF树结构不同结构中逻辑关系的对比V0V1V2V3V4图结构第10页/共167页无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。 图的基本术语 V0V1V2V0V1V2V36.1 图的逻辑结构第

6、11页/共167页含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？ 6.1 图的逻辑结构含有n个顶点的无向完全图有n(n-1)/2条边。 含有n个顶点的有向完全图有n(n-1)条边。 V0V1V2V3V0V1V2第12页/共167页稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD (v)。6.1 图的逻辑结构图的基本术语 顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD (v)。

7、第13页/共167页6.1 图的逻辑结构图的基本术语 在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？=niievTD12)(V0V1V2V3V4第14页/共167页V0V1V2V36.1 图的逻辑结构图的基本术语 在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？evODvIDiiii=11)()(nn第15页/共167页权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。6.1 图的逻辑结构图的基本术语 V0V1V2V32785哈夫曼树中的权与网图的权有何区别？7423第16页/共167页路径：在无向图G=(V,

8、E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2, , vim=vq)，其中，(vij-1,vij)E（1jm）。若G是有向图，则路径也是有方向的，顶点序列满足E。6.1 图的逻辑结构图的基本术语 一般情况下，图中的路径不惟一V0 到V3的路径： V0 V3 V0 V1 V2 V3 V0 V1 V4V2 V3V0V1V2V3V4第17页/共167页路径长度：6.1 图的逻辑结构图的基本术语 非带权图路径上边的个数带权图路径上各边的权之和V0 V3：长度为1V0 V1 V2 V3 ：长度为3V0 V1 V4V2 V3 ：长度为4V0V1V2V3V4第18页/共1

9、67页路径长度：6.1 图的逻辑结构图的基本术语 非带权图路径上边的个数带权图路径上各边的权之和V0 V3：长度为8V0 V1 V2 V3 ：长度为7V0 V1 V4 V2 V3 ：长度为15V0V1V2V3V4256328第19页/共167页回路（环）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。6.1 图的逻辑结构图的基本术语 V0V1V2V3V4V0V1V2V3第20页/共167页子图：若图G=（V，E），G=（V，E），如果VV 且E E ，则称图G是G的子图。6.1 图的逻辑结

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

11、，对图中任意一对顶点vi和vj (ij)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。 6.1 图的逻辑结构图的基本术语 如何求得一个非连通图的连通分量?第24页/共167页6.1 图的逻辑结构图的基本术语 V0V1V2V3强连通分量1 强连通分量2V0V2V3V1第25页/共167页生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。 生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。 如何理解极小连通子图?6.1 图的逻辑结构图的基本术

12、语 多构成回路少不连通含有n-1条边第26页/共167页V0V1V3V4V2V6V5V0V1V3V4V2V6V5V0V1V2V3V4V0V1V2V3V4生成树生成森林6.1 图的逻辑结构第27页/共167页图的抽象数据类型定义 ADT GraphData 顶点的有穷非空集合和边的集合Operation 6.1 图的逻辑结构图是一种与具体应用密切相关的数据结构，它的基本操作往往随应用不同而有很大差别。下面给出一个图的抽象数据类型定义的例子，简单起见，基本操作仅包含图的遍历，针对具体应用，需要重新定义其基本操作。第28页/共167页InitGraph 前置条件：图不存在 输入：无 功能：图的初始化

13、 输出：无 后置条件：构造一个空的图DestroyGraph 前置条件：图已存在 输入：无 功能：销毁图 输出：无 后置条件：释放图所占用的存储空间6.1 图的逻辑结构第29页/共167页 DFSTraverse 前置条件：图已存在 输入：遍历的起始顶点v 功能：从顶点v出发深度优先遍历图 输出：图中顶点的一个线性排列 后置条件：图保持不变 BFSTraverse 前置条件：图已存在 输入：遍历的起始顶点v 功能：从顶点v出发广度优先遍历图 输出：图中顶点的一个线性排列 后置条件：图保持不变endADT6.1 图的逻辑结构第30页/共167页图的遍历操作图的遍历是在从图中某一顶点出发，对图中所

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

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

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

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

18、V5V6V7V8 V1遍历序列：V1 V7V2V4V5V8V3 V3V6 V6V7第40页/共167页1. 深度优先遍历 从顶点v出发图的深度优先遍历算法的伪代码： 6.1 图的逻辑结构1. 访问顶点v; visitedv = 1;2. w =顶点v的第一个邻接点；3. while (w存在) 3.1 if (w未被访问) 从顶点w出发递归执行该算法; 3.2 w = 顶点v的下一个邻接点;第41页/共167页2. 广度优先遍历 基本思想： 访问顶点v； 依次访问v的各个未被访问的邻接点v1, v2, , vk； 分别从v1，v2，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接

19、点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。6.1 图的逻辑结构第42页/共167页广度优先遍历序列?入队序列?出队序列? 6.1 图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V1第43页/共167页广度优先遍历序列?入队序列?出队序列? 6.1 图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V2V3V3第44页/共167页广度优先遍历序列?入队序列?出队序列? 6.1 图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V3V4V4V5V5第45页/共167页广度优先遍历序列?入队序列?出队序列? 6.1

20、 图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V4V5V5V6V6V7V7第46页/共167页广度优先遍历序列?入队序列?出队序列? 6.1 图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V8第47页/共167页2. 广度优先遍历 6.1 图的逻辑结构从顶点v出发图的广度优先遍历算法的伪代码： 1. 初始化队列Q;2. 访问顶点v; visited v=1; 顶点v入队列Q;3. while (队列Q非空) 3.1 v=队列Q的队头元素出队; 3.2 w=顶点v的第一个邻接点; 3.3 while (w存在) 3.3

21、.1 如果w 未被访问，则 访问顶点w; visitedw=1; 顶点w入队列Q； 3.3.2 w=顶点v的下一个邻接点；第48页/共167页6.2 图的存储结构及实现是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。第49页/共167页邻接矩阵（数组表示法）基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。6.2 图的存储结构及实现假

22、设图G(V，E)有n个顶点，则邻接矩阵是一个nn的方阵，定义为：arcij1 若(vi, vj)E（或E）0 其它第50页/共167页无向图的邻接矩阵的特点？无向图的邻接矩阵6.2 图的存储结构及实现V0V2V3V1V0 V1 V2 V3vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V0 V1 V2 V3V0V1V2V3主对角线为 0 且一定是对称矩阵。第51页/共167页如何求顶点i的度？无向图的邻接矩阵6.2 图的存储结构及实现邻接矩阵的第i行（或第i列）非零元素的个数。0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V0 V

23、1 V2 V3V0V1V2V3V0V2V3V1V0 V1 V2 V3vertex=第52页/共167页如何判断顶点 i 和 j 之间是否存在边？无向图的邻接矩阵6.2 图的存储结构及实现测试邻接矩阵中相应位置的元素arcij是否为1。0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V0 V1 V2 V3V0V1V2V3V0V2V3V1V0 V1 V2 V3vertex=第53页/共167页如何求顶点 i 的所有邻接点？无向图的邻接矩阵6.2 图的存储结构及实现将数组中第 i 行元素扫描一遍，若arcij为1，则顶点 j 为顶点 i 的邻接点。V0V2V3V10 1 0

24、1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V0 V1 V2 V3V0V1V2V3V0 V1 V2 V3vertex=第54页/共167页6.2 图的存储结构及实现有向图的邻接矩阵V0V1V2V3V0 V1 V2 V3vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V0 V1 V2 V3V0V1V2V3有向图的邻接矩阵一定不对称吗？不一定，例如有向完全图。第55页/共167页6.2 图的存储结构及实现有向图的邻接矩阵如何求顶点 i 的出度？邻接矩阵的第 i 行元素之和。V0V1V2V3V0 V1 V2 V3vertex=0 1 1 0 0

25、0 0 0 0 0 0 1 1 0 0 0 arc=V0 V1 V2 V3V0V1V2V3第56页/共167页6.2 图的存储结构及实现有向图的邻接矩阵如何求顶点 i 的入度？邻接矩阵的第 i 列元素之和。V0V1V2V3V0 V1 V2 V3vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V0 V1 V2 V3V0V1V2V3第57页/共167页6.2 图的存储结构及实现有向图的邻接矩阵如何判断从顶点 i 到顶点 j 是否存在边？测试邻接矩阵中相应位置的元素arcij是否为1。V0V1V2V3V0 V1 V2 V3vertex=0 1 1 0 0 0 0

26、 0 0 0 0 1 1 0 0 0 arc=V0 V1 V2 V3V0V1V2V3第58页/共167页网图的邻接矩阵6.2 图的存储结构及实现网图的邻接矩阵可定义为： arcij wij 若(vi, vj)E（或E）0 若i=j 其他V0V1V2V32785 0 2 5 0 0 8 7 0 arc=第59页/共167页邻接矩阵存储无向图的类const int MaxSize=10; template class Mgraph public: MGraph(DataType a , int n, int e ); MGraph( ) void DFSTraverse(int v); void

27、BFSTraverse(int v); private: DataType vertexMaxSize; int arcMaxSizeMaxSize; int vertexNum, arcNum; ;6.2 图的存储结构及实现第60页/共167页邻接矩阵中图的基本操作构造函数 1. 确定图的顶点个数和边的个数；2. 输入顶点信息存储在一维数组vertex中；3. 初始化邻接矩阵；4. 依次输入每条边存储在邻接矩阵arc中； 4.1 输入边依附的两个顶点的序号i, j； 4.2 将邻接矩阵的第i行第j列的元素值置为1； 4.3 将邻接矩阵的第j行第i列的元素值置为1；6.2 图的存储结构及实现第

28、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.2 图的存储结构及实现邻接矩阵中图的基本操作构造函数

29、 第62页/共167页邻接矩阵中图的基本操作深度优先遍历template void MGraph : DFSTraverse(int v) cout vertexv; visitedv = 1; for (j = 0; j vertexNum; j+) if (arcvj = 1 & visitedj = 0) DFSTraverse( j );6.2 图的存储结构及实现第63页/共167页邻接矩阵中图的基本操作广度优先遍历template void MGraph : BFSTraverse(int v) front = rear = -1; /初始化顺序队列 cout vertexv

30、; visitedv = 1; Q+rear = v; while (front != rear) /当队列非空时 v = Q+front; /将队头元素出队并送到v中 for (j = 0; j vertexNum; j+) if (arcvj = 1 & visitedj = 0 ) cout vertexj; visitedj = 1; Q+rear = j; 6.2 图的存储结构及实现第64页/共167页邻接表邻接表存储的基本思想：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构

31、成了顶点表。 6.2 图的存储结构及实现图的邻接矩阵存储结构的空间复杂度？如果为稀疏图则会出现什么现象？ 假设图G有n个顶点e条边，则存储该图需要O(n2) 。第65页/共167页邻接表有两种结点结构：顶点表结点和边表结点。vertexfirstedge adjvex next 顶点表 边 表 vertex：数据域，存放顶点信息。 firstedge：指针域，指向边表中第一个结点。 adjvex：邻接点域，边的终点在顶点表中的下标。next：指针域，指向边表中的下一个结点。 6.2 图的存储结构及实现第66页/共167页struct ArcNode int adjvex; ArcNode *n

32、ext;template struct VertexNode DataType vertex; ArcNode *firstedge;定义邻接表的结点 6.2 图的存储结构及实现vertexfirstedge adjvex next第67页/共167页10323101 V0 V1 V2 V30123vertex firstedge6.2 图的存储结构及实现V0V2V3V1无向图的邻接表边表中的结点表示什么？每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。第68页/共167页6.2 图的存储结构及实现无向图的邻接表如何求顶点 i 的度？顶点i的边表中结点的个数。V0V2V3V1103

33、23101 V0 V1 V2 V30123vertex firstedge第69页/共167页如何判断顶点 i 和顶点 j之间是否存在边?测试顶点 i 的边表中是否存在终点为 j 的结点。6.2 图的存储结构及实现无向图的邻接表V0V2V3V110323101 V0 V1 V2 V30123vertex firstedge第70页/共167页6.2 图的存储结构及实现有向图的邻接表V0V1V2V31220 V0 V1 V2 V30123vertex firstedge如何求顶点 i 的出度？顶点 i 的出边表中结点的个数。第71页/共167页6.2 图的存储结构及实现有向图的邻接表如何求顶点

34、i 的入度？各顶点的出边表中以顶点 i 为终点的结点个数。V0V1V2V31220 V0 V1 V2 V30123vertex firstedge第72页/共167页6.2 图的存储结构及实现有向图的邻接表如何求顶点 i 的所有邻接点？遍历顶点 i 的边表，该边表中的所有终点都是顶点 i 的邻接点。V0V1V2V31220 V0 V1 V2 V30123vertex firstedge第73页/共167页6.2 图的存储结构及实现网图的邻接表V0V1V2V327852 1 V0 V1 V2 V30123vertex firstedge5 28 37 0第74页/共167页邻接表存储有向图的类c

35、onst int MaxSize = 10; /图的最大顶点数template class ALGraph public: ALGraph(DataType a , int n, int e); ALGraph; void DFSTraverse(int v); void BFSTraverse(int v); private: VertexNode adjlistMaxSize; int vertexNum, arcNum; ;6.2 图的存储结构及实现第75页/共167页邻接表中图的基本操作构造函数 1. 确定图的顶点个数和边的个数；2. 输入顶点信息，初始化该顶点的边表；3. 依次输入边

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

37、 第77页/共167页s for (k = 0; k ij; s = new ArcNode; s-adjvex = j; s-next = adjlisti.firstedge; adjlisti.firstedge = s; 6.2 图的存储结构及实现12 V0 V1 V2 V30123邻接表中图的基本操作构造函数 第78页/共167页邻接表中图的基本操作深度优先遍历template void ALGraph : DFSTraverse(int v) cout adjvex; if (visitedj = 0) DFSTraverse(j); p = p-next; 6.2 图的存储结构及

38、实现第79页/共167页邻接表中图的基本操作广度优先遍历template void ALGraph : BFSTraverse(int v) front = rear = -1; /初始化顺序队列 cout adjvex; if (visitedj = 0) cout next; 6.2 图的存储结构及实现第80页/共167页十字链表 邻接表6.2 图的存储结构及实现逆邻接表将邻接表与逆邻接表合二为一?为什么要合并？V0V1V2V312 3 0v0v1v2v301231 3 0 2 v0v1v2v3012303 第81页/共167页十字链表的结点结构vertexfirstinfirstout顶

39、点表结点tailvex headvex headlink taillink边表结点tailvex：弧的起点在顶点表中的下标；headvex：弧的终点在顶点表中的下标；headlink：入边表指针域；taillink：出边表指针域。6.2 图的存储结构及实现vertex：数据域，存放顶点信息；firstin：入边表头指针；firstout：出边表头指针；第82页/共167页3 03 1 3210V0V1V2V32 3 0 10 2 6.2 图的存储结构及实现十字链表存储有向图 V0V1V2V3v2v3v3v0v0v1v0v2v3v1第83页/共167页6.2 图的存储结构及实现邻接多重表存储无向

40、图 ivex ilink jvex jlinkvertexfirstedge(a)顶点表结点 (b) 边表结点 vertex：数据域，存储有关顶点的数据信息；firstedge：边表头指针，指向依附于该顶点的边表；ivex、jvex：与某条边依附的两个顶点在顶点表中的下标；ilink：指针域，指向依附于顶点ivex的下一条边；jlink：指针域，指向依附于顶点jvex的下一条边。第84页/共167页6.2 图的存储结构及实现邻接多重表存储无向图 V0V2V3V1第85页/共167页图的存储结构的比较邻接矩阵和邻接表O（n2）O（n+e）O（n2）O（n+e）空间性能 时间性能 适用范围 唯一性

41、邻接矩阵邻接表稠密图稀疏图唯一不唯一6.2 图的存储结构及实现第86页/共167页p 生成树的代价：设G = (V, E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。 p 最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。 6.3 最小生成树最小生成树的定义最小生成树的概念可以应用到许多实际问题中。例：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？ 第87页/共167页MST性质假设G=(V, E)是一个无向连通网，U是顶点集V的一个非空子集。若(u, v)是一条具有最小权值的

42、边，其中uU，vVU，则必存在一棵包含边(u, v)的最小生成树。顶点集UVUuvvu顶点集T1T26.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.3 最小生成树Prim算法的基本思想用伪代码描述如下：1. 初始化：U = v0； TE= ； 2. 重复下述操作直到U = V： 2.1 在E中寻找最短边(u，v)，且满足uU，vV-

43、U； 2.2 U = U + v； 2.3 TE = TE + (u，v)；关键:是如何找到连接U和V-U的最短边。 第89页/共167页U=A V-U=B, C, D, E, Fcost=(A, B)34, (A, C)46, (A, D),(A, E),(A, F)19 251234192646381725ABEDCFPrim算法 6.3 最小生成树第90页/共167页Prim算法 251234192646381725ABEDCFU=A, F V-U=B, C, D, Ecost=(A, B)34,(F, C)25, (F, D)25,(F, E)26 6.3 最小生成树第91页/共167

44、页Prim算法 2512341926381725ABEDCFU=A, F, C V-U=B, D, Ecost=(A, B)34, (C, D)17,(F, E)26 6.3 最小生成树第92页/共167页Prim算法 12341926381725ABEDCFU=A, F, C, D V-U=B, Ecost=(A, B)34, (F, E)26 6.3 最小生成树第93页/共167页Prim算法 123419261725ABEDCFU=A, F, C, D, E V-U=Bcost=(E, B)12 6.3 最小生成树第94页/共167页Prim算法 1219261725ABEDCFU=A,

45、 F, C, D, E, B V-U= 6.3 最小生成树第95页/共167页1. 图的存储结构：由于在算法执行过程中，需要不断读取任意两个顶点之间边的权值，所以，图采用邻接矩阵存储。数据结构设计6.3 最小生成树第96页/共167页251234192646381725ABEDCF对于顶点C，只需保留minarcAC, arcFC 6.3 最小生成树 2. 候选最短边集：设置数组shortEdgen表示候选最短边集，数组元素包括adjvex和lowcost两个域，分别表示候选最短边的邻接点和权值。 数据结构设计对于V-U中的每个顶点，只保留从该顶点到U中的某顶点的最短边。第97页/共167页p

46、 候选最短边(vi, vk)的权值为w，其中viV-U，vkU：如何用lowcost和adjvex表示候选最短边集？6.3 最小生成树shortEdgei.adjvex = kshortEdgei.lowcost = w数据结构设计shortEdgej.lowcost = min shortEdgej.lowcost , cost(vj，vk)shortEdgej.adjvex = k（如果边(vj，vk)的权值较小）p 顶点vk从集合V-U进入集合U后，依据下式更新数组shortEdge： 第98页/共167页1. 初始化两个辅助数组lowcost和adjvex；2. 输出顶点u0，将顶点u

47、0加入集合U中；3. 重复执行下列操作n-1次 3.1 在lowcost中选取最短边，取adjvex中对应的顶点序号k； 3.2 输出顶点k和对应的权值； 3.3 将顶点k加入集合U中； 3.4 调整数组lowcost和adjvex；Prim算法伪代码 6.3 最小生成树第99页/共167页克鲁斯卡尔（Kruskal）算法 基本思想：设无向连通网为G(V, E)，令G的最小生成树为T(U, TE)，其初态为UV，TE ，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个

48、连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。 6.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.3 最小生成树Kruskal算法的基本思想用伪代码描述如下

49、： 关键：如何判别被考察边的两个顶点是否位于两个连通分量 第101页/共167页251234192646381725ABEDCFABEDCF连通分量A, B, C, D, E, F6.3 最小生成树第102页/共167页251234192646381725ABEDCFABEDCF连通分量A, B, C, D, E, F12连通分量A, B, E, C, D, F6.3 最小生成树第103页/共167页251234192646381725ABEDCFABEDCF连通分量A, F, B, E, C, D12连通分量A, F, B, E, C, D176.3 最小生成树第104页/共167页2512

50、34192646381725ABEDCFABEDCF连通分量A, B, E, C, D, F12连通分量A, F, B, E, C, D196.3 最小生成树17第105页/共167页251234192646381725ABEDCFABEDCF连通分量A, F, B, E, C, D12连通分量A, F, C, D, B, E1917256.3 最小生成树第106页/共167页251234192646381725ABEDCFABEDCF连通分量A, F, C, D, B, E12连通分量A, F, C, D, B, E191725266.3 最小生成树第107页/共167页6.3 最小生成树1

51、. 图的存储结构：因为Kruskal算法是依次对图中的边进行操作，因此考虑用边集数组存储图中的边，为了提高查找速度，将边集数组按边上的权排序。 数据结构设计第108页/共167页6.3 最小生成树2. 连通分量。Kruskal算法实质上是使生成树以一种随意的方式生长，初始时每个顶点构成一棵生成树，然后每生长一次就将两棵树合并，到最后合并成一棵树。 因此，可以设置一个数组parentn，元素parenti表示顶点i的双亲结点，初始时，parenti= -1，表示顶点i没有双亲，即该结点是所在生成树的根结点；对于边(u, v)，设vex1和vex2分别表示两个顶点所在树的根结点，如果vex1vex

52、2，则顶点u和v必位于不同的连通分量，令parentvex2 = vex1，实现将两棵树合并。 求某顶点v所在生成树的根结点只需沿数组v = parentv不断查找v的双亲，直到parentv等于-1。 数据结构设计第109页/共167页6.3 最小生成树1. 初始化辅助数组parentn；num = 0；2. 依次考查每一条边for (i = 0; i arcNum; i+) 2.1 vex1 = edgei.from所在生成树的根结点； 2.2 vex2 = edgei.to所在生成树的根结点； 2.3 如果vex1 != vex2，执行下述操作： 2.3.1 parentvex2 = v

53、ex1; 2.3.2 num+; 2.3.3 if (num = n-1) 算法结束；数据结构设计Kruskal算法用伪代码进一步描述为： 第110页/共167页v1parent0=-1parent1=-1parent2=-1parent3=-1parent4=-1parent5=-16.3 最小生成树v5v0v4v3v2第111页/共167页v1parent0=-1parent1=-1parent2=-1parent3=-1parent4=1parent5=-16.3 最小生成树v5v0v4v3v212第112页/共167页v1parent0=-1parent1=-1parent2=-1pa

54、rent3=2parent4=1parent5=-16.3 最小生成树v5v0v4v3v21712第113页/共167页v1parent0=-1parent1=-1parent2=-1parent3=2parent4=1parent5=06.3 最小生成树v5v0v4v3v2171219第114页/共167页v1parent0=2parent1=-1parent2=-1parent3=2parent4=1parent5=06.3 最小生成树v5v0v4v3v217121925第115页/共167页v1parent0=2parent1=-1parent2=-1parent3=2parent4=1

55、parent5=06.3 最小生成树v5v0v4v3v217121925考查边(v3, v5)，由于parent3=2，parent2=-1，则v3所在生成树的根结点是v2 ，而parent5=0，parent0=2，则v5所在生成树的根结点也是v2 ，故舍去此边。第116页/共167页v1parent0=2parent1=-1parent2=1parent3=2parent4=1parent5=06.3 最小生成树v5v0v4v3v21712192526第117页/共167页在非网图中，最短路径是指两顶点之间经历的边数最少的路径。 6.4 最短路径最短路径 BAEDCAE：1ADE：2 AD

56、CE：3ABCE：3第118页/共167页最短路径 在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。 BAEDC105030101002060AE：100ADE：90 ADCE：60 ABCE：706.4 最短路径第119页/共167页问题描述：给定带权有向图G(V, E)和源点vV，求从v到G中其余各顶点的最短路径。 单源点最短路径问题 应用实例计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法Dijkstra算法。6.4 最短路径第120页/共167页基本

57、思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对viV-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, , vk，就将vk加入集合S中，并将路径v, , vk , vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。Dijkstra算法6.4 最短路径 集 合 V-S集合 Svkvvi第121页/共167页ABAEDC105030101002060S=AAB:(A, B)10AC:(A, C)AD: (A, D)30AE: (A, E)100Dijkstra算法6.4 最短路径第122页/共16

58、7页ABAEDC105030101002060S=A, BAB:(A, B)10AC:(A, B, C)60AD: (A, D)30AE: (A, E)100BDijkstra算法6.4 最短路径第123页/共167页ABAEDC105030101002060S=A, B, DAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, E)90BDDijkstra算法6.4 最短路径第124页/共167页ABAEDC105030101002060S=A, B, D, CAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A,

59、D, C, E)60BDCDijkstra算法6.4 最短路径第125页/共167页ABAEDC105030101002060Dijkstra算法S=A, B, D, C, EAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, C, E)60BDCE6.4 最短路径第126页/共167页p图的存储结构：带权的邻接矩阵存储结构 p数组distn：每个分量disti表示当前所找到的从始点v到终点vi的最短路径的长度。初态为：若从v到vi有弧，则disti为弧上权值；否则置disti为。p数组pathn：pathi是一个字符串，表示当前所找到的从始点v到终

60、点vi的最短路径。初态为：若从v到vi有弧，则pathi为vvi；否则置pathi空串。p数组sn：存放源点和已经生成的终点，其初态为只有一个源点v。 数据结构 :6.4 最短路径第127页/共167页1. 初始化数组dist、path和s；2. while (s中的元素个数n) 2.1 在distn中求最小值，其下标为k； 2.2 输出distj和pathj； 2.3 修改数组dist和path； 2.4 将顶点vk添加到数组s中；Dijkstra算法伪代码6.4 最短路径第128页/共167页每一对顶点之间的最短路径 问题描述：给定带权有向图G(V, E)，对任意顶点vi,vjV（ij），求顶点vi到顶点