国家级精品课程—《数据结构与算法》 第7章图 张铭、赵海燕、王腾蛟、宋国杰、高军 http:/www.ipk.pku.edu.cn/pkuipk/courselsig 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:王腾蛟 版权所有,转载或翻印必究
国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：王腾蛟 ©版权所有，转载或翻印必究 第7章 图
主要内容 7.1图的定义和术语 72图的抽象数据类型 7.3图的存储结构 74图的周游 7.5最短路径 76最小生成树 77图知识点总结 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主要内容 ◼ 7.1 图的定义和术语 ◼ 7.2 图的抽象数据类型 ◼ 7.3 图的存储结构 ◼ 7.4 图的周游 ◼ 7.5 最短路径 ◼ 7.6 最小生成树 ◼ 7.7 图知识点总结
71图的定义和术语 图( Graph)由表示数据元素的集合V和表示数据之间关 系的集合E组成,记为G= 在图中,数据元素通常称作顶点( vertex),V就是顶点 的有穷非空集合 顶点的序偶,称之为边edge),E是边的集合 有向图、带权图、稀疏图、稠密图、完全图、连通图 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 图(Graph)由表示数据元素的集合V和表示数据之间关 系的集合E组成，记为G = ◼ 在图中，数据元素通常称作顶点(vertex)，V就是顶点 的有穷非空集合 ◼ 顶点的序偶，称之为边(edge)，E是边的集合 ◼ 有向图、带权图、稀疏图、稠密图、完全图、连通图
71图的定义和术语 若代表一条边的顶点序偶是无序的(即该边无方向), 则称此图为无向图。 若代表一条边的顶点序偶是有序的(即边有方向),则 称此图为有向图。 (a)无向图G1 (b)有向图G2 图7.2图的示例 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 若代表一条边的顶点序偶是无序的(即该边无方向)， 则称此图为无向图。 ◼ 若代表一条边的顶点序偶是有序的(即边有方向)，则 称此图为有向图。 图7.2 图的示例 v0 v2 v3 v1 v4 v0 v2 v1 v3 (a) 无向图G1 (b) 有向图G2
71图的定义和术语 通常用n表示图中顶点的数目,用e表示边或弧的数 目。无向图中e的取值范围是从0到n(n-1)2,有向 图中e的取值范围是从0到n(n-1) 边数相对较少的图称为稀疏图( sparse graph) 边数相对较多的图称为稠密图( dense graph) 任何两顶点间都有边相关联的图称为完全图 ( complete graph),完全图显然具有最大的边数 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 通常用n表示图中顶点的数目，用e表示边或弧的数 目。无向图中e的取值范围是从0到n(n - 1)/2，有向 图中e的取值范围是从0到n(n - 1) ◼ 边数相对较少的图称为稀疏图(sparse graph) ◼ 边数相对较多的图称为稠密图(dense graph) ◼ 任何两顶点间都有边相关联的图称为完全图 (complete graph)，完全图显然具有最大的边数
71图的定义和术语 A A B A A B B C B D (a)无向完全图 (b)有向完全图 图73完全图 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 A B C A C B D A B C A C B D （a）无向完全图 （b）有向完全图 图7.3 完全图
71图的定义和术语 设G=是一个图,若E'是E的子集,V是ⅴ的子集 ,且E'中的边仅与V中顶点相关联,则图G′=(V,E)称 为图G的子图( (subgraph) (a)无向图G (b)有向图G2 (a)无向图G的若干子图 b)有向图G2的若千子图 图74图72的若于子图 “十一五”国家级规划教材。张铭,王胳蚊,赵嗨￡,《数捃豬构与算法》,高教社,20〗.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 设G = 是一个图，若E′是E的子集，V′是V的子集 ，且E′中的边仅与V′中顶点相关联，则图G′= (V′,E′)称 为图G的子图(subgraph)。 v0 v0 v2 v3 v1 v4 v0 v2 v3 v0 v1 v3 （a）无向图 G1的若干子图 （b）有向图 G2的若干子图 图7.4 图7.2的若干子图 v0 v2 v3 v1 v4 v0 v2 v1 v3 (a) 无向图G1 (b) 有向图G2
71图的定义和术语 无向图G=中从顶点vp到顶点vq的路径(path)是 个顶点序列(vp=vm,vn,v2,…,vm=v),其中(v1 ,v;)∈E,1≤j≤m。若G是有向图,则路径也是有向的 ,顶点序列应满足1,v>∈E,1≤j≤m 路径长度( length)定义为路径上的边(或弧)的数目 第一个顶点和最后一个顶点相同的路径称为回路或环 (cycle) 序列中顶点不重复出现的路径称为简单路径( simple path) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 无向图G = 中从顶点vp到顶点vq的路径(path)是一 个顶点序列(vp = vi0，vi1，vi2，…，vim = vq )，其中(vij-1 ，vij)∈E，1 ≤ j ≤ m。若G是有向图，则路径也是有向的 ，顶点序列应满足∈E，1 ≤ j ≤ m ◼ 路径长度(length)定义为路径上的边（或弧）的数目 ◼ 第一个顶点和最后一个顶点相同的路径称为回路或环 (cycle) ◼ 序列中顶点不重复出现的路径称为简单路径(simple path)
71图的定义和术语 除了第一个顶点和最后一个顶点外,其余顶点不重复 的回路,称为简单回路( simple cycle) 不带回路的图称为无环图 acyclic graph) 不带回路的有向图称为有向无环图( directed acyclic graph,简记为DAG) 一个有向图中,若存在一个顶点v,从此顶点有路径 可以到达图中其他所有顶点,则称此有向图为有根的 图,v称作图的根 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 除了第一个顶点和最后一个顶点外，其余顶点不重复 的回路，称为简单回路(simple cycle) ◼ 不带回路的图称为无环图(acyclic graph) ◼ 不带回路的有向图称为有向无环图(directed acyclic graph，简记为DAG) ◼ 一个有向图中，若存在一个顶点v0，从此顶点有路径 可以到达图中其他所有顶点，则称此有向图为有根的 图，v0称作图的根
71图的定义和术语 在无向图中,如果从顶点v到顶点v;有路径,则称v和v是连通的 (connected) 如果对于图中的任意两个顶点vnv∈V,v和v都是连通的,则称无向 图G为连通图。 连通分量( connected component)定义为无向图中的极大连通子图。 (a)非连通的无向图G3 (b)非连通无向图G3的连通分量 图75非连通无向图的连通分量示意图 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj是连通的 (connected)。 ◼ 如果对于图中的任意两个顶点vi ,vj∈V，vi和vj都是连通的，则称无向 图G 为连通图。 ◼ 连通分量(connected component)定义为无向图中的极大连通子图。 v0 v2 v1 v3 v5 v6 v7 v8 v4 v0 v2 v1 v3 v5 v6 v7 v8 v4 (a) 非连通的无向图G3 （b） 非连通无向图G3的连通分量 图7.5 非连通无向图的连通分量示意图