数据结构课件-图讲述

《数据结构课件-图讲述》由会员分享，可在线阅读，更多相关《数据结构课件-图讲述（125页珍藏版）》请在金锄头文库上搜索。

1、Page 1* p 画出下列二叉链表代表的二叉树（0代表NULL指针），并 完成其先序线索链表 InfoABCDEFGHIJKLMN Ltag Lchild24607010012130000 Rtag Rchild3500891100014000 InfoABCDEFGHIJKLMN Ltag00010101001111 Lchild246273101412131391011 Rtag00110001110111 Rchild3565891131213140118 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Page 2* 数据结构数据结构 第8-1讲 图的基础知识 清华

2、大学 自动化系 黄双喜 博士、副教授 huangsx Page 3* q学习目标 v领会图的基本概念。 v熟悉图的各种存储结构及其构造算法，了解各种存储 结构的特点及其选用原则。 v熟练掌握图的两种遍历算法及应用。 v理解各种图的应用问题的算法。 q重点和难点 v重点：图的各种应用问题的算法都比较经典，注意理 解各种图的算法及其应用场合。 Page 4* q知识点 v图的类型定义 v图的存储表示 v图的深度优先搜索遍历和广度优先搜索遍历 v最小生成树算法 v拓扑排序 v关键路径 v最短路径 图的基础知识图的基础知识 q图的概念与基本术语 q图的类型定义与存储 q图的遍历 q图的连通性与最小生成

3、树 Page 5* * 欧拉1707年出生在瑞士的巴塞尔城，19岁开始发 表论文，直到76岁。几乎每一个数学领域都可以 看到欧拉的名字，从初等几何的欧拉线，多面体 的欧拉定理，立体解析几何的欧拉变换公式，四 次方程的欧拉解法到数论中的欧拉函数，微分方 程的欧拉方程，级数论的欧拉常数，复变函数的 欧拉公式等等。据统计他那不倦的一生，共写下 了886本书籍和论文，其中分析、代数、数论占 40%，几何占18%，物理和力学占28%，天文 学占11%，弹道学、航海学、建筑学等占3%。 1733年，年仅26岁的欧拉担任了彼得堡科学院 数学教授。1741年到柏林担任科学院物理数学所 所长，直到1766年，重

4、回彼得堡，没有多久，完 全失明。欧拉在数学上的建树很多，对著名的哥 尼斯堡七桥问题的解答开创了图论的研究。 图论图论欧拉欧拉 Page 7* 能否从某个地方出发，穿过所有的桥仅一次 后再回到出发点？ 哥尼斯堡七桥问题哥尼斯堡七桥问题 18世纪东普鲁士哥尼斯堡被普列戈 尔河分为四块, 它们通过七座桥相互 连接。当时该城的市民热衷于这样 一个游戏：“一个散步者怎样才能从 某块陆地出发，经每座桥一次且仅 一次回到出发点？” * C A D B 七桥问题的图模型 欧拉回路的判定规则： 1.如果通奇数桥的地方多于 两个，则不存在欧拉回路； 2.如果只有两个地方通奇数 桥，可以从这两个地方之一 出发，找到

5、欧拉回路； 3.如果没有一个地方是通奇 数桥的，则无论从哪里出发 ，都能找到欧拉回路。 Page 9* 最短路问题（SPPshortest path problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙 地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名 司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这 一问题相当于需要找到一条从甲地到乙地的最短路。 旅行商问题（TSPtraveling salesman problem） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一 条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返 回驻地）？这一问

6、题的研究历史十分悠久，通常称之为旅行商问题 。 中国邮递员问题（CPPChinese postman problem） 一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最 短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后 返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所 以国际上称之为中国邮递员问题。 运输问题(transportation problem) 某种原材料有N个产地，现在需要将原材料从产地运往M个使用这 些原材料的工厂。假定N个产地的产量和M家工厂的需要量已知，单 位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案 可以使总运输成本最低

7、？ 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连 接起来，使得从其中任何一个城市都可以经高速公路直接或间接到 达另一个城市。假定已经知道了任意两个城市之间修建高速公路的 成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最 小？ 上述问题有两个共同的特点： 一、 它们的目的都是从若干可能的安排或方案中 寻求某种意义下的最优安排或方案，数学上把这种问题 称为最优化或优化（optimization）问题； 二、 它们都易于用图形的形式直观地描述和表达 ，数学上把这种与图相关的结构称为网络（network） 。 与图和网络相关的最优化问题就是网络最优化或称网络最优化或

8、称 网络优化网络优化 （network optimizationnetwork optimization）问题）问题。 q线性表 v每个数据元素只有一个直接前驱和一个直接后继。 q树形结构 v每个数据元素只有一个直接前驱，但可能有多个直接后继。 q图形结构 v每个数据元素可能有多个直接前驱和多个直接后继。 图是比线性表和树复杂的数据结构，广泛应用于计 算机、逻辑学、物理、化学等领域。 图的基本特性 网络拓扑结构社交网络 图像处理物理化学结构电脑游戏 * 图的定义 图是由顶点的有穷非空集合和顶点之间边的集合组 成，通常表示为： G=(V，E) 其中：G表示一个图，V是图G中顶点的集合，E是 图G

9、中顶点之间边的集合。 在线性表中，元素个数可以为零，称为空表； 在树中，结点个数可以为零，称为空树； 在图中，顶点个数不能为零，但可以没有边。 Page 15 如果图的任意两个顶点之间的边都 是无向边，则称该图为无向图。 若顶点vi和vj之间的边没有方向，则 称这条边为无向边，表示为(vi,vj)。 若从顶点vi到vj的边有方向，则称这 条边为有向边，表示为。 如果图的任意两个顶点之间的边都 是有向边，则称该图为有向图。 V1V2 V3 V4V5 V1V2 V3V4 图的基本术语 Page 16 简单图：在图中，若不存在顶点到其自身的边，且同 一条边不重复出现。 V3 V4V5 V1V2 V3

10、 V4V5 V1V2 非简单图 非简单图 简单图 V1V2 V3 V4V5 v 数据结构中讨论的都是简单图 。 邻接、依附 无向图中，对于任意两个顶点vi和顶点vj，若存在边 (vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边 (vi，vj)依附于顶点vi和顶点vj。 V1V2 V3 V4V5 V1的邻接点： V2的邻接点： V2 、V4 V1 、V3 、V5 * 邻接、依附 有向图中，对于任意两个顶点vi和顶点vj，若存在弧 ，则称顶点vi邻接到顶点vj，顶点vj邻接自顶 点vi，同时称弧依附于顶点vi和顶点vj 。 V1V2 V3V4 V1的邻接点： V3的邻接点： V2 、V3

11、V4 * 无向完全图：在无向图中，如果任意两个顶点之 间都存在边，则称该图为无向完全图。 有向完全图：在有向图中，如果任意两个顶点之间 都存在方向相反的两条弧，则称该图为有向完全图 。 V1V2 V3 V1V2 V3V4 * 含有n个顶点的无向完全图有多少条边？ 含有n个顶点的有向完全图有多少条弧？ 含有n个顶点的无向完全图有n(n-1)/2条边。 含有n个顶点的有向完全图有n(n-1)条边。 V1V2 V3 V1V2 V3V4 * 稀疏图：称边数很少的图为稀疏图； 稠密图：称边数很多的图为稠密图。 顶点的度：在无向图中，顶点v的度是指依附于该顶 点的边数，通常记为TD (v)。 顶点的入度：

12、在有向图中，顶点v的入度是指以该顶 点为弧头的弧的数目，记为ID (v)； 顶点的出度：在有向图中，顶点v的出度是指以该顶 点为弧尾的弧的数目，记为OD (v)。 * V1V2 V3 V4V5 在具有n个顶点、e条边的无向图G中，各顶点 的度之和与边数之和的关系？ = = n i i evTD 1 2)( V1V2 V3V4 在具有n个顶点、e条边的有向图G中，各顶点 的入度之和与各顶点的出度之和的关系？与边 数之和的关系？ evODvID i i i i = =11 )()( nn * 权：是指对边赋予的有意义的数值量。 网：边上带权的图，也称网图。 V1V2 V3V4 2 7 8 5 图结

13、构中的权和哈夫曼树中的权有什么区别？ * 路径：在无向图G=(V, E)中，从顶点vp到顶点vq之间 的路径是一个顶点序列(vp=vi0,vi1,vi2, , vim=vq)，其 中，(vij-1,vij)E（1jm）。若G是有向图，则路径 也是有方向的，顶点序列满足E。 V1V2 V3 V4V5 一般情况下，图中两个顶点之间的路径不唯一。 在什么情况下唯一？ V1 到V4的路径： V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4 * 路径长度： 非带权图路径上边的个数 带权图路径上各边的权之和 V1V2 V3 V4V5 V1 V4：长度为1 V1 V2 V3 V4 ：长度为3

14、V1 V2 V5V3 V4 ：长度为4 * 路径长度： 非带权图路径上边的个数 带权图路径上各边的权之和 V1 V4：长度为8 V1 V2 V3 V4 ：长度为7 V1 V2 V5V3 V4 ：长度为15 V1V2 V3 V4V5 2 5 6 3 2 8 * 回路（环）：第一个顶点和最后一个顶点相同的路径。 简单路径：序列中顶点不重复出现的路径。 简单回路（简单环）：除了第一个顶点和最后一个顶点外 ，其余顶点不重复出现的回路。 V1V2 V3 V4V5 V1V2 V3V4 * 子图：若图G=（V，E），G=（V，E），如果 VV 且E E ，则称图G是G的子图。 V1V2 V3 V4V5 V1

15、V2 V3 V4V5 V1 V3 V4 * 连通图：在无向图中，如果从一个顶点vi到另一个顶 点vj(ij)有路径，则称顶点vi和vj是连通的。如果图中 任意两个顶点都是连通的，则称该图是连通图。 连通分量：非连通图的极大连通子图称为连通分量。 如何求得一个非连通图的连通分量? 1.含有极大顶点数； 2. 依附于这些顶点的所有边。 * 连通分量1 V1V2 V3 V4V5 V6 V7 V1V2 V4V5 V3V6 V7 连通分量2 v连通分量是对无向图的一种划分。 Page 32* 强连通图：在有向图中，对图中任意一对顶点vi和vj (ij)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路

16、径 ，则称该有向图是强连通图。 强连通分量：非强连通图的极大强连通子图。 如何求得一个有向非连通图的强连通分量? * V1V2 V3V4 强连通分量1 强连通分量2 V1 V3V4 V2 * 生成树：n个顶点的连通图G的生成树是包含G中全部 顶点的一个极小连通子图。 生成森林：在非连通图中，由每个连通分量都可以得 到一棵生成树，这些连通分量的生成树就组成了一个 非连通图的生成森林。 如何理解极小连通子图? 多构成回路 少不连通 含有n-1条边 * V1V2 V3 V4V5 V6 V7 V1V2V3 V4V5 V6 V7 V1V2 V3 V4V5 V1V2 V3 V4V5 生成树 生成森林 图的基础知识图的基础知识 q图的概念与基本术语 q图的类型定义与存储 q图的遍历 q图的连通性与最小生成树 Page 36* * 图的抽象数据类型定义如下： ADT Graph 数据对象V ：V