北京大学：《数据结构与算法》课程教学资源（PPT课件讲稿）图

第六章图 任课教员:张铭 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 图的基本概念（续） 无向图示例 有向图示例

61图的基本概念(续) 标号图( labeled graph) 带权图( weighted graph) 15 北京大学信息学院 版权所有,转载或翻印必究 Page 6

北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 6.1 图的基本概念（续） ◼ 标号图（labeled graph） ◼ 带权图（weighted graph）

61图的基本概念(续) 顶点的度( degree) 与该顶点相关联的边的数目 入度( n degree 出度( out degree) ■子图( subgraph) 图G=(V,E,G’=(V,E)中,若V≤V, E’≤E,并且E中的边所关联的顶点都在v 中,则称图G是图G的子图 北京大学信息学院 版权所有,转载或翻印必究 Page 7

北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 6.1 图的基本概念（续） ◼ 顶点的度（degree） ◼ 与该顶点相关联的边的数目。 ◼ 入度(in degree) ◼ 出度(out degree) ◼ 子图（subgraph） ◼ 图G=(V，E)，G’=(V’ ，E’)中，若V’≤V， E’≤E，并且E’中的边所关联的顶点都在V’ 中，则称图G’是图G的子图

61图的基本概念(续) a路径(path) 在图G=(v,E)中,如果存在顶点序列v vn,Va,…,Vn,V,使得(v,V1) Vn,V)(若对有向图 则使得,,…,)都在E中,则称从顶点v到顶点v存 在一条路径 简单路径( simple path) 路径长度( length) 北京大学信息学院 版权所有,转载或翻印必究 Page 8

北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 6.1 图的基本概念（续） ◼ 路径（path） ◼ 在图G=(V，E)中，如果存在顶点序列Vp， Vi1，Vi2，…，Vin，Vq，使得（Vp，Vi1）， (Vi1，Vi2) ，…，(Vin，Vq)（若对有向图， 则使得， ，…，）都在E中，则称从顶点Vp到顶点Vq存 在一条路径。 ◼ 简单路径（simple path） ◼ 路径长度（length）

61图的基本概念(续) 回路( cycle,也称为环) 简单回路( simple cycle) 无环图( acyclic graph) 有向无环图( directed acyclic graph,简写为DAG 北京大学信息学院 版权所有,转载或翻印必究 Page 9

北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 6.1 图的基本概念（续） ◼ 回路（cycle，也称为环） ◼ 简单回路（simple cycle） ◼ 无环图（acyclic graph） ◼ 有向无环图（directed acyclic graph，简写为DAG）

61图的基本概念(续) 有根的图 个有向图中,若存在一个顶点v,从此顶点 有路径可以到达图中其它所有顶点,则称此有 向图为有根的图,V称作图的根。 连通的( connected) 对无向图G=(V,E)而言,如果从V1到V2有 条路径(从V2到V1也一定有一条路径) 称V1和V2是连通的( connected) 强连通 北京大学信息学院 版权所有,转载或翻印必究 Page 10

北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 6.1 图的基本概念（续） ◼ 有根的图 ◼ 一个有向图中，若存在一个顶点V0，从此顶点 有路径可以到达图中其它所有顶点，则称此有 向图为有根的图，V0称作图的根。 ◼ 连通的（connected） ◼ 对无向图G=（V，E）而言，如果从V1到V2有 一条路径（从V2到V1也一定有一条路径），则 称V1和V2是连通的（connected） 。 ◼ 强连通