数据结构与算法 第六章图 任课教员:张铭 http://db.pku.edu.cn/mzhang/ds/ zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究
数据结构与算法 第六章 图 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究
主要内容 61图的基本概念 令62图的抽象数据类型 令63图的存储结构 64图的周游(深度、广度、拓扑) 令6.5最短路径问题 66最小支撑树 北京大学信息学院 版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 2 主要内容 6.1 图的基本概念 6.2 图的抽象数据类型 6.3 图的存储结构 6.4 图的周游（深度、广度、拓扑） 6.5 最短路径问题 6.6 最小支撑树
61图的基本概念 G=(V,E)表示 V是顶点( vertex)集合 E是边(edge)的集合 边的始点 边的终点 稀疏图( sparse graph) 密集图( dense graph) V4 完全图( complete graph) 北京大学信息学院 版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 3 6.1 图的基本概念 G=（V，E）表示 V是顶点（vertex）集合 E是边（edge）的集合 边的始点 边的终点 稀疏图（sparse graph） 密集图（dense graph） 完全图（complete graph）
无向图 边涉及顶点的偶 对无序 实际上是双通 北京大学信息学院 版权所有,转载或翻印必究 Page 4
北京大学信息学院 ©版权所有，转载或翻印必究 Page 4 无向图 边涉及顶点的偶 对无序 实际上是双通
有向图 有向图( directed graph或 digraph 边涉及顶点的偶对是有序的 北京大学信息学院 版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 5 有向图 有向图（directed graph或 digraph） 边涉及顶点的偶对是有序的