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