0467.cC
海量文库 文档专家
当前位置:首页 >> >>

数据结构第6章图精品资料_图文

4/13/2019 1 of 169 第 6章 图 本章的主要内容是: 图的逻辑结构 图的存储结构及实现 图的连通性 最小生成树 最短路径 AOV网与拓扑排序 AOE网与关键路径 4/13/2019 2 of 169 第6 章 图 图是一种非常复杂的非线性结构,并且具有极强的表达能力, 现实世界中的许多问题都可以抽象为图结构。本章是本课程 的难点和重点。通过本章的学习,要求学生: ?掌握图的定义及其基本术语; ?理解图的抽象数据类型定义; ?掌握图的邻接矩阵和邻接表存储; ?掌握图的遍历方法及其在邻接矩阵和邻接表存储结构上的实现; ?理解图的十字链表、邻接多重表和边集数组存储方法; ?理解无向图的连通性; ?了解有向图的连通性; ?掌握Prim算法和Kruskal算法的基本思想和求解过程; ?理解Prim算法和Kruskal算法的C++描述; ?掌握Dijkstra算法和Floyd算法的基本思想及求解过程; ?理解Dijkstra算法和Floyd算法的C++描述; ?掌握拓扑序列的定义及拓扑排序算法; ?掌握关键路径的定义及求解过程; ?理解求关键路径算法。 4/13/2019 3 of 169 图论——欧拉 欧拉1707年出生在瑞士的巴塞尔城,19岁开始发 表论文,直到76岁。几乎每一个数学领域都可以 看到欧拉的名字,从初等几何的欧拉线,多面体 的欧拉定理,立体解析几何的欧拉变换公式,四 次方程的欧拉解法到数论中的欧拉函数,微分方 程的欧拉方程,级数论的欧拉常数,变分学的欧 拉方程,复变函数的欧拉公式等等。据统计他那 不倦的一生,共写下了886本书籍和论文,其中 分析、代数、数论占40%,几何占18%,物理和 力学占28%,天文学占11%,弹道学、航海学、 建筑学等占3%。 1733年,年仅26岁的欧拉担任 了彼得堡科学院数学教授。1741年到柏林担任科 学院物理数学所所长,直到1766年,重回彼得堡, 没有多久,完全失明。欧拉在数学上的建树很多, 对著名的哥尼斯堡七桥问题的解答开创了图论的 研究。 4/13/2019 4 of 169 哥尼斯堡七桥问题 能否从某个地方出发,穿过所有的桥仅一次 后再回到出发点? 4/13/2019 5 of 169 哥尼斯堡七桥问题 七桥问题的图模型 C 欧拉回路的判定规则: 1.如果通奇数桥的地方多于 两个,则不存在欧拉回路; 2.如果只有两个地方通奇数 桥,可以从这两个地方之一 出发,找到欧拉回路; 3.如果没有一个地方是通奇 数桥的,则无论从哪里出发, 都能找到欧拉回路。 A B D 4/13/2019 6 of 169 6.1 图的逻辑结构 图的定义 图是由顶点的有穷非空集合和顶点之间边的集合组 成,通常表示为: G=(V,E) 其中:G表示一个图,V是图G中顶点的集合,E是 图G中顶点之间边的集合。 在线性表中,元素个数可以为零,称为空表; 在树中,结点个数可以为零,称为空树; 在图中,顶点个数不能为零,但可以没有边。 4/13/2019 7 of 169 6.1 图的逻辑结构 V1 V3 V4 V1 V2 若顶点vi和vj之间的边没有方向,则 称这条边为无向边,表示为(vi,vj)。 V5 如果图的任意两个顶点之间的边都 是无向边,则称该图为无向图。 V2 若从顶点vi到vj的边有方向,则称这 条边为有向边,表示为<vi,vj>。 V4 如果图的任意两个顶点之间的边都 是有向边,则称该图为有向图。 V3 4/13/2019 8 of 169 6.1 图的逻辑结构 图的基本术语 简单图:在图中,若不存在顶点到其自身的边,且同 一条边不重复出现。 V1 V2 V1 V3 V2 V1 V3 V2 V3 V4 非简单图 V5 V4 非简单图 V5 V4 简单图 V5 ? 数据结构中讨论的都是简单图。 4/13/2019 9 of 169 6.1 图的逻辑结构 图的基本术语 邻接、依附 无向图中,对于任意两个顶点 vi和顶点 vj,若存在边 (vi, vj) ,则称顶点 vi和顶点 vj互为邻接点,同时称边 (vi,vj)依附于顶点vi和顶点vj。 V1 V1的邻接点: V2 、V4 V2的邻接点: V1 、V3 、V5 V2 V3 V4 V5 4/13/2019 10 of 169 6.1 图的逻辑结构 图的基本术语 邻接、依附 有向图中,对于任意两个顶点 vi和顶点 vj,若存在弧 <vi, vj>,则称顶点 vi邻接到顶点 vj,顶点 vj邻接自顶 点vi,同时称弧<vi,vj>依附于顶点vi和顶点vj 。 V1 V2 V1的邻接点: V2 、V3 V3的邻接点: V4 V3 V4 4/13/2019 11 of 169 不同结构中逻辑关系的对比 A B A D 线性结构 V1 C E F V2 V3 B D E C F V4 V5 图结构 树结构 在线性结构中,数据元素之间仅具有线性关系; 在树结构中,结点之间具有层次关系; 在图结构中,任意两个顶点之间都可能有关系。 4/13/2019 12 of 169 不同结构中逻辑关系的对比 A B A D 线性结构 V1 C E F V2 V3 B D E C F V4 V5 图结构 树结构 在线性结构中,元素之间的关系为前驱和后继; 在树结构中,结点之间的关系为双亲和孩子; 在图结构中,顶点之间的关系为邻接。 4/13/2019 13 of 169 6.1 图的逻辑结构 图的基本术语 无向完全图:在无向图中,如果任意两个顶点之间 都存在边,则称该图为无向完全图。 有向完全图:在有向图中,如果任意两个顶点之间 都存在方向相反的两条弧,则称该图为有向完全图 。 V2 V1 V2 V1 V3 V4 V3 4/13/2019 14 of 169

网站首页 | 网站地图
All rights reserved Powered by 0467资源网 0467.cc
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。liunxqq@126.com