中国药科大学：《数据结构》 第7章 图和广义表2

第7章图和广义表 计算机教研宦 第1页 2021/2/19

Data Structure 数据结构—— 第7章图和广义表 胡建华 2021/2/19 计算机教研室 第 1 页 第 7 章 图和广义表

@7.1图的定义和基本术语 图( Graph)G是由两个集合V和E组成的偶对,表示为 G=(V, E) 其中V是有限非空的顶点集合,E是由顶点偶对表示的关系集合。 为了讨论方便,有时也将顶点集合为空的图称为空图。Q 个图可以形式化定义为: G=(V, E) V={v|v∈ data object} E={v,w>v,w∈V∧P(v,w) 其中v是数据元素,称为顶点( vertex),P(v,w表示从顶点v 到顶点W有一条直接通路,即v和w之间存在一个关系,用顶点偶对 回来表示。 通常可以根据图的顶点偶对将图分为有向图和无向图 计算机教研宦 第2页 2021/2/19

Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第2页 7.1 图的定义和基本术语 ▪ 图(Graph)G是由两个集合V和E组成的偶对,表示为 G=（V，E） 其中V是有限非空的顶点集合，E是由顶点偶对表示的关系集合。 为了讨论方便，有时也将顶点集合为空的图称为空图。 ▪ 一个图可以形式化定义为： G=（V，E） V={v|v data object} E={| v,w V∧P(v,w)} 其中v是数据元素，称为顶点（vertex），P(v,w)表示从顶点v 到顶点w有一条直接通路，即v和w之间存在一个关系，用顶点偶对 来表示。 通常可以根据图的顶点偶对将图分为有向图和无向图。 A D E F C B

@有向图 如下图(a)是一个有向图G,可形式地表示为 G=(V,E v=a, b, c, d, el E={,,,,,,,v,w是顶点,v为弧尾,w为弧头 C (a)有向图G 计算机教研宦 第3页 2021/2/19

Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第3页 有向图 如下图(a)是一个有向图G，可形式地表示为： G=(V,E) V={a，b，c，d，e} E={，，，，，，，} E是有向边（也称弧）的有限集合，弧是顶点的有序对，记为 ，v,w是顶点，v为弧尾，w为弧头 b c d e a （a) 有向图G

@无向图 如图(b)所示的是一个无向图G,可形式地表示为: G=(V, E) v=a, b,c, d E={(a,b),(a,c),(a,d),(b,d),(c,d)} EG)是边的有限集合,边是顶点的无序对,记为(v,w)或(w,V), 缩并且(vm=(wy (b)无向图G 计算机教研宦 第4页 2021/2/19

Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第4页 无向图 如图(b)所示的是一个无向图G，可形式地表示为： G=(V,E) V={a，b，c，d} E = {(a,b),(a,c),(a,d),(b,d),(c,d)} E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)， 并且（v,w)=(w,v) c b d a (b) 无向图G

有向完备图一n个顶点的有向图最大边数是n(n-1) 无向完备图—n个顶点的无向图最大边数是n(n-1)/2 例 有向完备图 无向完备图 若边或弧的个数e< nlogn,则称作稀疏图,否则称作稠密图。 计算机教研宦 第5页 2021/2/19

Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第5页 ▪ 有向完备图——n个顶点的有向图最大边数是n(n-1) ▪ 无向完备图——n个顶点的无向图最大边数是n(n-1)/2 例 2 1 3 2 1 3 有向完备图 无向完备图 若边或弧的个数 e<nlogn，则称作稀疏图，否则称作稠密图

权—与图的边或弧相关的数叫权 网——带权的图叫网 61 39 2 3 81 个带权有向图 计算机教研宦 第6页 2021/2/19

Data Structure 数据结构—— 第7章图和广义表 胡建华 2021/2/19 计算机教研室 第 6 页 ▪ 权——与图的边或弧相关的数叫权 ▪ 网——带权的图叫网 一个带权有向图 1 2 61 3 81 9 5 5 2 4 3 1

子图——如果图G(V,E)和图G(V,E),满足: ●EcE 则称G为G的子图 例 图与子图 计算机教研宦 第7页 2021/2/19

Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第7页 ▪ 子图——如果图G(V,E)和图G‘(V’,E‘),满足： ⚫ V’ V ⚫ E’ E 则称G‘为G的子图 3 5 6 例 2 4 5 1 3 6 图与子图

顶点的度 无向图中,顶点的度TD为与每个顶点相连的边数 有向图中,顶点的度分成入度与出度 入度ID:以该顶点为头的弧的数目 出度OD:以该顶点为尾的弧的数目 例 2 G2 G1 顶点5的度: 顶点2入度:1出度:3 顶点2的度: 顶点4入度:1出度:0 计算机教研宦 第8页 2021/2/19

Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第8页 ▪ 顶点的度 ▪ 无向图中，顶点的度TD为与每个顶点相连的边数 ▪ 有向图中，顶点的度分成入度与出度 ▪ 入度ID：以该顶点为头的弧的数目 ▪ 出度OD：以该顶点为尾的弧的数目 例 2 4 5 1 3 6 G1 顶点2入度：1 出度：3 顶点4入度：1 出度：0 例 1 5 7 3 2 4 G2 6 顶点5的度：3 顶点2的度：4

路径——路径是顶点的序列V={10V1,…Vn),满足(V11,V1)E或 V1,V13>∈E,(1<js 路径长度—沿路径边的数目或沿路径各边权值之和 回路——第一个顶点和最后一个顶点相同的路径叫回路 简单路径——一序列中顶点不重复出现的路径叫 简单回路——除了第一个顶点和最后一个顶点外,其余顶点不重复出现 的回路叫~ 例 路径 路径长度:5 简单路径:1,2,3,5 回路:1,2,3 简单回路:3,5,6,3 例 路径:1,2,5,7,6,5,2,3 路径长度:7 简单路径:1,2,5,7,6 回路:1,2,5,7,6,5,2,1 简单回路:1,2,3,量算机教研室 第9页 g2 2021/2/19

Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第9页 ▪ 路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E 或 E,(1<jn) ▪ 路径长度——沿路径边的数目或沿路径各边权值之和 ▪ 回路——第一个顶点和最后一个顶点相同的路径叫回路 ▪ 简单路径——序列中顶点不重复出现的路径叫~ ▪ 简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现 的回路叫~ 例 1 5 7 3 2 4 G2 6 例 2 4 5 1 3 6 G1 路径：1，2，3，5，6，3 路径长度：5 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3 路径：1，2，5，7，6，5，2，3 路径长度：7 简单路径：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 简单回路：1，2，3，1

连通——从顶点V到顶点W有一条路径,则说V和W是连通的 连通图—图中任意两个顶点都是连通的叫 连通分量—非连通图的每一个连通部分叫 强连通图——有向图中,如果对每一对V,Vj∈V,ViVj,从ⅵ到 Vj和从Vj到Ⅵi都存在路径,则称G是 例 例 强连通图 连通图 例 非连通图 连通分量 计算机教研宦 第10页 2021/2/19

Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第10页 ▪ 连通——从顶点V到顶点W有一条路径，则说V和W是连通的 ▪ 连通图——图中任意两个顶点都是连通的叫~ ▪ 连通分量——非连通图的每一个连通部分叫~ ▪ 强连通图——有向图中，如果对每一对Vi,VjV, ViVj,从Vi到 Vj 和从Vj到 Vi都存在路径，则称G是~ 连通图 例 2 4 5 1 3 6 强连通图 3 5 6 例 非连通图 连通分量 例 2 4 5 1 3 6