国家级精品课程—《数据结构与算法》 第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=<V,E> 在图中,数据元素通常称作顶点( vertex),V就是顶点 的有穷非空集合 顶点的序偶,称之为边edge),E是边的集合 有向图、带权图、稀疏图、稠密图、完全图、连通图 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 图(Graph)由表示数据元素的集合V和表示数据之间关 系的集合E组成，记为G = <V，E> ◼ 在图中，数据元素通常称作顶点(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)，完全图显然具有最大的边数