资源预览内容
第1页 / 共191页
第2页 / 共191页
第3页 / 共191页
第4页 / 共191页
第5页 / 共191页
第6页 / 共191页
第7页 / 共191页
第8页 / 共191页
第9页 / 共191页
第10页 / 共191页
亲,该文档总共191页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
,Page 1,2018/9/4,第七章 图,Page 2,2018/9/4,学习目标 领会图的类型定义。 熟悉图的各种存储结构及其构造算法,了解各种存储结构的特点及其选用原则。 熟练掌握图的两种遍历算法。 理解各种图的应用问题的算法。 重点和难点 重点:图的各种应用问题的算法都比较经典,注意理解各种图的算法及其应用场合。,Page 3,2018/9/4,知识点 图的类型定义 图的存储表示 图的深度优先搜索遍历和广度优先搜索遍历 无向网的最小生成树 拓扑排序 关键路径 最短路径,Page 4,2018/9/4,欧拉1707年出生在瑞士的巴塞尔城,19岁开始发表论文,直到76岁。几乎每一个数学领域都可以看到欧拉的名字,从初等几何的欧拉线,多面体的欧拉定理,立体解析几何的欧拉变换公式,四次方程的欧拉解法到数论中的欧拉函数,微分方程的欧拉方程,级数论的欧拉常数,变分学的欧拉方程,复变函数的欧拉公式等等。据统计他那不倦的一生,共写下了886本书籍和论文,其中分析、代数、数论占40%,几何占18%,物理和力学占28%,天文学占11%,弹道学、航海学、建筑学等占3%。 1733年,年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长,直到1766年,重回彼得堡,没有多久,完全失明。欧拉在数学上的建树很多,对著名的哥尼斯堡七桥问题的解答开创了图论的研究。,图论欧拉,Page 5,2018/9/4,能否从某个地方出发,穿过所有的桥仅一次后再回到出发点?,哥尼斯堡七桥问题,Page 6,2018/9/4,七桥问题的图模型,欧拉回路的判定规则: 1.如果通奇数桥的地方多于两个,则不存在欧拉回路; 2.如果只有两个地方通奇数桥,可以从这两个地方之一出发,找到欧拉回路; 3.如果没有一个地方是通奇数桥的,则无论从哪里出发,都能找到欧拉回路。,Page 7,2018/9/4,图的定义,图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为: G=(V,E) 其中:G表示一个图,V是图G中顶点的集合,E是图G中顶点之间边的集合。,在线性表中,元素个数可以为零,称为空表; 在树中,结点个数可以为零,称为空树; 在图中,顶点个数不能为零,但可以没有边。,7.1 图的定义和术语,Page 8,2018/9/4,线性表 每个数据元素只有一个直接前驱和一个直接后继。 树形结构 每个数据元素只有一个直接前驱,但可能有多个直接后继。 图形结构 每个数据元素可能有多个直接前驱和多个直接后继。,图是比线性表和树复杂的数据结构,广泛应用于语言学、逻辑学、物理、化学等领域。,Page 9,2018/9/4,如果图的任意两个顶点之间的边都是无向边,则称该图为无向图。,若顶点vi和vj之间的边没有方向,则称这条边为无向边,表示为(vi,vj)。,若从顶点vi到vj的边有方向,则称这条边为有向边,表示为。,如果图的任意两个顶点之间的边都是有向边,则称该图为有向图。,图的基本术语,Page 10,2018/9/4,简单图:在图中,若不存在顶点到其自身的边,且同一条边不重复出现。,数据结构中讨论的都是简单图。,Page 11,2018/9/4,图的基本术语,邻接、依附 无向图中,对于任意两个顶点vi和顶点vj,若存在边(vi,vj),则称顶点vi和顶点vj互为邻接点,同时称边(vi,vj)依附于顶点vi和顶点vj。,V1的邻接点: V2 、V4 V2的邻接点: V1 、V3 、V5,Page 12,2018/9/4,图的基本术语,邻接、依附 有向图中,对于任意两个顶点vi和顶点vj,若存在弧,则称顶点vi邻接到顶点vj,顶点vj邻接自顶点vi,同时称弧依附于顶点vi和顶点vj 。,V1的邻接点: V2 、V3 V3的邻接点: V4,Page 13,2018/9/4,无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。,有向完全图:在有向图中,如果任意两个顶点之间都存在方向相反的两条弧,则称该图为有向完全图。,图的基本术语,Page 14,2018/9/4,含有n个顶点的无向完全图有多少条边? 含有n个顶点的有向完全图有多少条弧?,含有n个顶点的无向完全图有n(n-1)/2条边。 含有n个顶点的有向完全图有n(n-1)条边。,Page 15,2018/9/4,稀疏图:称边数很少的图为稀疏图; 稠密图:称边数很多的图为稠密图。,顶点的度:在无向图中,顶点v的度是指依附于该顶点的边数,通常记为TD (v)。,图的基本术语,顶点的入度:在有向图中,顶点v的入度是指以该顶点为弧头的弧的数目,记为ID (v); 顶点的出度:在有向图中,顶点v的出度是指以该顶点为弧尾的弧的数目,记为OD (v)。,Page 16,2018/9/4,图的基本术语,在具有n个顶点、e条边的无向图G中,各顶点的度之和与边数之和的关系?,Page 17,2018/9/4,图的基本术语,在具有n个顶点、e条边的有向图G中,各顶点的入度之和与各顶点的出度之和的关系?与边数之和的关系?,Page 18,2018/9/4,权:是指对边赋予的有意义的数值量。 网:边上带权的图,也称网图。,图的基本术语,Page 19,2018/9/4,路径:在无向图G=(V, E)中,从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2, , vim=vq),其中,(vij-1,vij)E(1jm)。若G是有向图,则路径也是有方向的,顶点序列满足E。,图的基本术语,一般情况下,图中的路径不惟一。,V1 到V4的路径: V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4,Page 20,2018/9/4,路径长度:,图的基本术语,非带权图路径上边的个数 带权图路径上各边的权之和,V1 V4:长度为1 V1 V2 V3 V4 :长度为3 V1 V2 V5V3 V4 :长度为4,Page 21,2018/9/4,路径长度:,图的基本术语,非带权图路径上边的个数 带权图路径上各边的权之和,V1 V4:长度为8 V1 V2 V3 V4 :长度为7 V1 V2 V5V3 V4 :长度为15,Page 22,2018/9/4,回路(环):第一个顶点和最后一个顶点相同的路径。 简单路径:序列中顶点不重复出现的路径。 简单回路(简单环):除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路。,图的基本术语,Page 23,2018/9/4,子图:若图G=(V,E),G=(V,E),如果VV 且E E ,则称图G是G的子图。,图的基本术语,Page 24,2018/9/4,连通图:在无向图中,如果从一个顶点vi到另一个顶点vj(ij)有路径,则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的,则称该图是连通图。 连通分量:非连通图的极大连通子图称为连通分量。,图的基本术语,如何求得一个非连通图的连通分量?,Page 25,2018/9/4,V1,V2,V3,V4,V5,V6,V7,图的基本术语,连通分量是对无向图的一种划分。,Page 26,2018/9/4,强连通图:在有向图中,对图中任意一对顶点vi和vj (ij),若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径,则称该有向图是强连通图。 强连通分量:非强连通图的极大强连通子图。,图的基本术语,如何求得一个非连通图的连通分量?,Page 27,2018/9/4,图的基本术语,V1,V2,Page 28,2018/9/4,生成树:n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。,生成森林:在非连通图中,由每个连通分量都可以得到一棵生成树,这些连通分量的生成树就组成了一个非连通图的生成森林。,如何理解极小连通子图?,图的基本术语,Page 29,2018/9/4,Page 30,2018/9/4,图的抽象数据类型定义如下: ADT Graph 数据对象V :V是具有相同特性的数据元素的集合,称为顶 点集。 数据关系R : R=VR VR| v,wV且P(v,w),表示从v到w的 弧,谓词P(v,w)定义了弧的意义 或信息 ,Page 31,2018/9/4,G1=(V1, VR1) V1 = A, B, C, D, E VR1=, ,G2=(V2, VR2) V2=A, B, C, D, E, F VR2=(A,B),(A,E),(B,E),(C,D), (D,F),(B,F),(C,F) ,Page 32,2018/9/4,CreateGraph( 初始条件:图 G 存在,u 和 G 中顶点有相同特征。 操作结果:若 G 中存在和 u 相同的顶点,则返回该顶点 在图中位置;否则返回其它信息。,Page 33,2018/9/4,GetVex(G, v); 初始条件:图 G 存在,v 是 G 中某个顶点。 操作结果:返回 v 的值。 FirstAdjVex(G, v); 初始条件:图 G 存在,v 是 G 中某个顶点。 操作结果:返回 v 的第一个邻接点。若该顶点在 G 中没 有邻接点,则返回“空”。 NextAdjVex(G, v, w); 初始条件:图 G 存在,v 是 G 中某个顶点,w 是 v 的 邻接顶点。 操作结果:返回 v 的(相对于 w 的)下一个邻接点。若 w 是 v 的最后一个邻接点,则返回“空”。,Page 34,2018/9/4,PutVex( 初始条件:图 G 存在,v 是 G 中某个顶点。 操作结果:删除 G 中顶点 v 及其相关的弧。,Page 35,2018/9/4,InsertArc( 初始条件:图 G 存在,v 和 w 是 G 中两个顶点。 操作结果:在 G 中删除弧,若 G 是无向的,则还 删除对称弧。,Page 36,2018/9/4,DFSTraverse(G, Visit(); 初始条件:图 G 存在,Visit 是顶点的应用函数。 操作结果:对图 G 进行深度优先遍历。遍历过程中对每 个顶点调用函数Visit 一次且仅一次。一旦 visit() 失败,则操作失败。 FSTraverse(G, Visit(); 初始条件:图 G 存在,Visit 是顶点的应用函数。 操作结果:对图 G 进行广度优先遍历。遍历过程中对每 个顶点调用函数Visit 一次且仅一次。一旦 visit() 失败,则操作失败。 ADT Graph,Page 37,2018/9/4,是否可以采用顺序存储结构存储图?,图的特点:顶点之间的关系是m:n,即任何两个顶点之间都可能存在关系(边),无法通过存储位置表示这种任意的逻辑关系,所以,图无法采用顺序存储结构。,如何存储图?,考虑图的定义,图是由顶点和边组成的,分别考虑如何存储顶点、如何存储边。,7.2 图的存储结构,Page 38,2018/9/4,7.2 图的存储结构,数组表示法(邻接矩阵) 将图的顶点信息存储在一个一维数组中,并将它的邻接矩阵存储在一个二维数组中即构成图的数组表示。 假设图中顶点数为n,则邻接矩阵A定义为,网的邻接矩阵的定义为,当vi到vj有弧相邻接时,aij的值应为该弧上的权值,否则为。,Page 39,2018/9/4,图的数组(邻接矩阵)存储表示 #define INFINITY INT_MAX; / 最大值 #define MAX_VERTEX_NUM 20; / 最大顶点个数 typedef enum DG,DN,UDG,UDN GraphKind;/ 有向图,有向网,无向图,无向网 typedef struct ArcCell VRType adj; / VRType是顶点关系类型。对无权图,用1或0 / 表示相邻否;对带权图,则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; / 顶点信息 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 MGraph;,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号