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