数据结构与算法 第六章图 任课教员:张铭 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） 边涉及顶点的偶对是有序的
标号图( abeled graph) 带权图( weighted graph) 3 15 4 V 6 北京大学信息学院 版权所有,转载或翻印必究 Page 6
北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 标号图（labeled graph） 带权图（weighted graph）
顶点的度( degree) 与该顶点相关联的边的数目 入度( in degree) 出度( out degree) 北京大学信息学院 散权所伺,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 顶点的度（degree） 与该顶点相关联的边的数目 入度(in degree) 出度(out degree)
子图( subgraph) n图G=(V,E,G'=(V,E)中,若V≤V, E≤E,并且E中的边所关联的顶点都在V 中,则称图G是图G的子图 V 北京大学信息学院 版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 子图（subgraph） 图G=(V，E)，G’=(V’，E’)中，若V’≤V， E’≤E，并且E’中的边所关联的顶点都在V’ 中，则称图G’是图G的子图
路径(path) p 从顶点vp到顶点vq的路径 顶点序列V,vn,Va,… 使得(vn,V1) vn,V),…,(m,V)(若 对有向图,则使得 )都在E中 ■简单路径( simple path) q 路径长度( length) 北京大学信息学院 版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 路径（path） 从顶点Vp到顶点Vq的路径 顶点序列Vp，Vi1，Vi2，…， Vin，Vq，使得（Vp，Vi1）， (Vi1，Vi2) ，…，(Vin，Vq)（若 对有向图，则使得， ，…， ）都在E中 简单路径（simple path） 路径长度（length） Vp Vq
回路( cycle,也称为环) 无向图中,如果两个结点之间有平行边, 容易让人误看作“环”) 路径长度大于等于3 n有向图两条边可以构成环,例如 和构成环 0 北京大学信息学院 @版权所有,转载或翻印必究 Page 10
北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 回路（cycle，也称为环） 无向图中，如果两个结点之间有平行边， 容易让人误看作“环”） 路径长度大于等于3 有向图两条边可以构成环，例如 和 构成环 V0 ╳ √ √ V1√