中国科学技术大学：《数据结构及其算法》课程电子教案（PPT课件讲稿）第7章 图（主讲：刘东）

第7章图 7.1图的基本概念 7.2图的表示与实现 7.3图的遍历 7.4最小生成树 7.5拓扑排序 7.6关键路径 7.7最短路径 2021/2/11 数据结构及其算法第7章图

第7章 图 •7.1 图的基本概念 •7.2 图的表示与实现 •7.3 图的遍历 •7.4 最小生成树 •7.5 拓扑排序 •7.6 关键路径 •7.7 最短路径 2021/2/11 数据结构及其算法 第7章 图 2

7.1图的基本概念 图( graph):任意两个数据元素之间可以存在关系 的数据结构 线性表:前驱、后继关系 树:双亲、孩子关系 图论( graph theory):数学和计算机科学中研究 图状结构的理论 〔柯尼斯堡七桥问题 图码 欧拉,1736年 的整还 2021/2/11 数据结构及其算法第7章图

7.1 图的基本概念 •图(graph)：任意两个数据元素之间可以存在关系 的数据结构 • 线性表：前驱、后继关系 • 树：双亲、孩子关系 •图论(graph theory)：数学和计算机科学中研究 图状结构的理论 2021/2/11 数据结构及其算法 第7章 图 3 柯尼斯堡七桥问题 欧拉，1736年

范甘迪 麦迪麦蒂尔斯通 叶莉 乌鲁木齐 哈尔滨 呼和浩特 668 图的实例 397 社交网络:微博、人人 674 交通网 计划路线图 1100 639贵 672|675 洗开水壶(1分钟 烧开水(15分钟) 洗荼壶(1分钟 洗荼杯(2分钟) 拿荼叶(1分钟 2021/2/11 数据结构及其算法第7章图

•图的实例 • 社交网络：微博、人人 • 交通网 • 计划路线图 2021/2/11 数据结构及其算法 第7章 图 4

·图的数学模型:G=(V,E) ⅴ:图中数据元素的集合,称顶点(ⅴ ertex)集 E:图中数据之间关系的集合,称边(edge)集 数据之间的关系可以是单向的,也可以是双向的 有向图( digraph):单向数据关系。此时边又称弧 (arc),从弧尾到弧头 无向图( undigraph):双向数据关系 边上可以附带数字,称为权( weight),带权的图 又称网( network) (a)有向图 (b)无向图 (b) 2021/2/11 数据结构及其算法第7章图

•图的数学模型：G=(V,E) • V：图中数据元素的集合，称顶点(vertex)集 • E：图中数据之间关系的集合，称边(edge)集 •数据之间的关系可以是单向的，也可以是双向的 • 有向图(digraph)：单向数据关系。此时边又称弧 (arc)，从弧尾到弧头 • 无向图(undigraph)：双向数据关系 •边上可以附带数字，称为权(weight)，带权的图 又称网(network) 2021/2/11 数据结构及其算法 第7章 图 5 (a) 有向图 (b) 无向图

图的基本操作 创建、销毁 遍历:深度优先、广度优先 对顶点的操作:增加、删除、访间、修改 对边的操作:增加、删除、访问、修改权 ADT Graph(课本PP.215~217) 2021/2/11 数据结构及其算法第7章图

•图的基本操作 •创建、销毁 •遍历：深度优先、广度优先 •对顶点的操作：增加、删除、访问、修改 •对边的操作：增加、删除、访问、修改权 •ADT Graph (课本PP.215~217) 2021/2/11 数据结构及其算法 第7章 图 6

顶点和边 顶点通过边邻接,边依附于顶点 不考虑顶点到自身有边的情况 n个顶点的有向图,最大边数为n(n-1) n个顶点的无向图,最大边数为n(n-1)/2 达到最大边数的图称为完全( complete)图,边数 接近完全的图称为稠密( dense)图,边数远小于完 全的图称为稀疏( sparse)图 每个顶点所关联的边的数目称为度( degree) 有向图中又分为入度( indegree)和出度( outdegree) 顶点的度和图的边数满足e=∑=1D(v) 2021/2/11 数据结构及其算法第7章图

•顶点和边 •顶点通过边邻接，边依附于顶点 •不考虑顶点到自身有边的情况 • n个顶点的有向图，最大边数为n(n-1) • n个顶点的无向图，最大边数为n(n-1)/2 •达到最大边数的图称为完全(complete)图，边数 接近完全的图称为稠密(dense)图，边数远小于完 全的图称为稀疏(sparse)图 •每个顶点所关联的边的数目称为度(degree) • 有向图中又分为入度(indegree)和出度(outdegree) •顶点的度和图的边数满足𝑒 = 1 2 σ𝑖=1 𝑛 𝐷(𝑣𝑖 ) 2021/2/11 数据结构及其算法 第7章 图 7

例 顶点数:4 边数:4 V1的入度1,出度2 V4的入度1,出度1 柯尼斯堡七桥问题无解, 顶点数:5 因为顶点的度都是奇数 边数:6 V1的度2 V4的度2 2021/2/11 数据结构及其算法第7章图

•例 2021/2/11 数据结构及其算法 第7章 图 8 顶点数：4 边数：4 V1的入度1，出度2 V4的入度1，出度1 顶点数：5 边数：6 V1的度2 V4的度2 柯尼斯堡七桥问题无解， 因为顶点的度都是奇数

子图( subgraph) .g=(,Ei G=(v,ei VCv,Ece yih (a) 2021/2/11 数据结构及其算法第7章图

•子图(subgraph) •𝐺 = (𝑉, 𝐸); 𝐺 ′ = (𝑉 ′ ,𝐸′); 𝑉 ′ ⊆ 𝑉, 𝐸′ ⊆ 𝐸 2021/2/11 数据结构及其算法 第7章 图 9

路径和连通 路径(path):图中两顶点(ⅴ,v′)之间的路径是 个顶点序列,序列的首元为v,末元为v′,序列中 后两元之间的边在图中存在 路径的长度是路径中的边的数目 ⅴ=v′的路径称为回路或环( cycle 序列中顶点无重复的路径称为简单路 连通:若路径(ⅴ,v)存在,则称ⅴ与v′连通 任意两个顶点均连通的无向图称为连通图 任意一对顶点均连通的有向图称为强连通图 2021/2/11 数据结构及其算法第7章图 10

•路径和连通 •路径(path)：图中两顶点(v,v’)之间的路径是一 个顶点序列，序列的首元为v，末元为v’，序列中 前后两元之间的边在图中存在 • 路径的长度是路径中的边的数目 • v=v’的路径称为回路或环(cycle) • 序列中顶点无重复的路径称为简单路径 •连通：若路径(v,v’)存在，则称v与v’连通 •任意两个顶点均连通的无向图称为连通图 •任意一对顶点均连通的有向图称为强连通图 2021/2/11 数据结构及其算法 第7章 图 10

例 (Ⅵ1,V3,V4,Ⅵ1,V2)是一条路径, 长度为4 不是简单路径(V1重复) (V1,V3,V4,V1)是一条简单环 不是强连通图 (Ⅵ1,V2,V3,5)是一条路径, ④长度为3, 是简单路径 (V2,v3,V5,V2)是一条简单环 是连通图 2021/2/11 数据结构及其算法第7章图 11

•例 2021/2/11 数据结构及其算法 第7章 图 11 (V1,V3,V4,V1,V2)是一条路径， 长度为4， 不是简单路径(V1重复) (V1,V3,V4,V1)是一条简单环 不是强连通图 (V1,V2,V3,V5)是一条路径， 长度为3， 是简单路径 (V2,V3,V5,V2)是一条简单环 是连通图