北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第六章 图

数据结构与算法 第六章图 任课教员:张铭 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√