中南大学：《数据结构》课程教学资源（PPT课件讲稿）第七章 图

第七章图 本章介绍另一种非线性数据结构 图 图:是一种多对多的结构关系,每个元素可以有零 或多个直接前趋;零个或多个直接后继;

本章介绍另一种非线性数据结构 —— 图 图：是一种多对多的结构关系，每个元素可以有零 个或多个直接前趋；零个或多个直接后继；

血第七章图 7.1图的概念 7.2图的存储结构 7.3图的遍历 7.4生成树 7.5最短路径 7.6拓扑排序

 第七章 图 7.1 图的 概念 7.2 图的存储结构 7.3 图的遍历 7.4 生成树 7.5 最短路径 7.6 拓扑排序

第七章图 学习要点 1.熟悉图的各种存储结构及其构造算法,了解实际问题的求 解效率与采用何种存储结构和算法有密切联系; 2.熟练掌握图的两种遍历:深度优先遍历和广度优先遍历的 算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似 和差异。树的先根遍历是一种深度优先搜索策略,树的层次遍历 是一种广度优先搜索策略 3.理解课件中讨论的各种图的算法;

第七 章 图 学习要点 1．熟悉图的各种存储结构及其构造算法，了解实际问题的求 解效率与采用何种存储结构和算法有密切联系； 2．熟练掌握图的两种遍历：深度优先遍历和广度优先遍历的 算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似 和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历 是一种广度优先搜索策略 3．理解课件中讨论的各种图的算法；

第七章图 ⑩7.1图的概念 图的概念 图的应用 图的基本操作 四图的基本术语

 7.1 图的概念 一 图的概念 二 图的应用 三 图的基本操作 四 图的基本术语 第七 章 图

§71图的基本概念 图的概念 图的定义 图G由两个集合构成,记作G=其中V是顶点的非空有限集合,E是边 的有限集合,其中边是顶点的无序对或有序对集合。 例 G1= V1=vo,v 1V2,V3,V4 E1={(vo,v1),(V,V3),( V1,V V。,V 2 2V4 无序对(v,Vy): 用连接顶点vV的线段 V4) 表示,称为无向边; G图示

§7.1 图的基本概念 一 图的概念 图的定义 图G由两个集合构成，记作G= 其中V是顶点的非空有限集合，E是边 的有限集合，其中边是顶点的无序对或有序对集合。 G1= V1={v0 ,v1,v2,v3,v4 } E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)} G1图示 无序对(vi,vj)： 用连接顶点vi、vj的线段 表示，称为无向边； 例 V0 V3 V4 V1 V2

§71图的基本概念 G2= V2={vov1,2,v3 E2={,,,: V2) V3 用以为v;起点、以v;为终点 的有向线段表示,称为有向 G2图示 边或弧; 无向图:在图G中,若所有边是无向边,则称G为无向图; 有向图:在图G中,若所有边是有向边,则称G为有向图; 混和图:在图G中,即有无向边也有有向边,则称G为混合图;

G2 图示 有序对 ： 用以为vi起点、以vj为终点 的有向线段表示，称为有向 边或弧； 无向图：在图G中，若所有边是无向边，则称G为无向图； 有向图：在图G中，若所有边是有向边，则称G为有向图； 混和图：在图G中，即有无向边也有有向边，则称G为混合图； §7.1 图的基本概念 V0 V1 V2 V3 G2= V2={v0 v1,v2,v3} E2={ , , ,}

§71图的基本概念 二图的应用举例 例1交通图(公路、铁路) 顶点:地点 边:连接地点的公路 交通图中的有单行道双行道,分别用有向边、无向边表示; 例2电路图 顶点:元件 VO 边:连接元件之间的线路 例3通讯线路图 (v2 顶点:地点 V3 边:地点间的连线 例4各种流程图 如产品的生产流程图 顶点:工序 边:各道工序之间的顺序关系 V

二 图的应用举例 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示； 例2 电路图 顶点：元件 边：连接元件之间的线路 例3 通讯线路图 顶点：地点 边：地点间的连线 例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系 §7.1 图的基本概念 V0 V3 V4 V1 V2 V0 V1 V2 V3

§71图的基本概念 图的基本术语 1邻接点及关联边 邻接点:边的两个顶点 关联边:若边e=(v,u),则称顶点v、u关连边e 2顶点的度、入度、出度 V3) V4) 顶点V的度=与V相关联的边的数目 在有向图中: 顶点V的出度=以V为起点有向边数 顶点V的入度=以V为终点有向边数 顶点V的度=V的出度+V的入度 设图G的顶点数为n,边数为e 图的所有顶点的度数和=2*e V3) (每条边对图的所有顶点的度数和“贡献”2度)

1 邻接点及关联边 邻接点：边的两个顶点 关联边：若边e= (v, u), 则称顶点v、u 关连边e 2 顶点的度、入度、出度 顶点V的度 = 与V相关联的边的数目 在有向图中： 顶点V的出度=以V为起点有向边数 顶点V的入度=以V为终点有向边数 顶点V的度= V的出度+V的入度 设图G的顶点数为n，边数为e 图的所有顶点的度数和 = 2*e （每条边对图的所有顶点的度数和“贡献”2度） e 三 图的基本术语 §7.1 图的基本概念 V0 V3 V4 V1 V2 V0 V1 V2 V3

§71图的基本概念 3路径、回路 无向图G=(V,E)中的顶点序列v1,V2,,Ⅴk,若 (vi,vi+1)∈E(i=1,2,…kx-1),ⅴ=v1,u=vk,则称该序列是 从顶点v到顶点u的路径;若v=u,则称该序列为回路 有向图D=(V,E)中的顶点序列v1,v2,…,vk,若 ∈E(i=1,2,…kx-1),ⅴ=v1,u=vk,则称该序列是 从顶点v到顶点u的路径;若v=u,则称该序列为回路; 例 在图1中,V0,Ⅵ1,V2,V3是V0到V3的路径;V0,V1,V2,V3,V0是回 路;在图2中,V0,V2,V3是V0到V3的路径;VO,V2,V3,V0是回 路 无向图G1 V2 有向图G2 V3) V3

3 路径、回路 无向图G=（V，E）中的顶点序列v1,v2,… ,vk,若 (vi,vi+1)E( i=1,2,…k-1), v =v1, u =vk, 则称该序列是 从顶点v到顶点u的路径；若v=u，则称该序列为回路； 有向图D=（V，E）中的顶点序列v1,v2,… ,vk, 若 E (i=1,2,…k-1), v =v1, u =vk, 则称该序列是 从顶点v到顶点u的路径；若v=u，则称该序列为回路； 在图1中，V0,V1,V2,V3 是V0到V3的路径； V0,V1,V2,V3,V0是回 路；在图2中，V0,V2,V3 是V0到V3的路径； V0,V2,V3,V0是回 路； 无向图G1 有向图G2 例 §7.1 图的基本概念 V0 V3 V4 V1 V2 V0 V1 V2 V3

§71图的基本概念 3简单路径和简单回路 在一条路径中,若除起点和终点外,所有顶点各不相同,则称 该路径为简单路径; 由简单路径组成的回路称为简单回路; 例 在图1中,V0,Ⅵ1,V2,V3是简单路径;V0,V1,V2,V4,Ⅵ不是 简单路径;在图2中,V0,V2,V3,V0是简单回路; VO 无向图G1 有向图G2 V3) V3

3 简单路径和简单回路 在一条路径中,若除起点和终点外,所有顶点各不相同,则称 该路径为简单路径； 由简单路径组成的回路称为简单回路； 在图1中，V0,V1,V2,V3 是简单路径； V0,V1,V2,V4,V1不是 简单路径；在图2中， V0,V2,V3,V0是简单回路； 无向图G1 有向图G2 例 §7.1 图的基本概念 V0 V3 V4 V1 V2 V0 V1 V2 V3