第5单元 非线性数据结构 图 计算机软件基础 The software bas ic of computer 讲:刘志 西安交通大学 计算机教学实验中心
下一页 计算机软件基础 The software basic of computer 主讲：刘志强 西安交通大学 计算机教学实验中心 第5单元 非线性数据结构 图
教学目标 ●了解有关图的 基本概念 存储结构及实现 遍历算法 □上一页 停止放映 第2页
下一页 上一页 停止放映 第 2 页 教学目标 ⚫ 了解有关图的 –基本概念 –存储结构及实现 –遍历算法
教学要求 ●通过本单元学习,了解、掌握有关图: 基本概念 有向图、无向图、连通图、网 存储结构及实现 邻接矩阵、邻接表 遍历及其它操作 □上一页 °深度优先、广度优先遍历 停止放映 应用 第3页
下一页 上一页 停止放映 第 3 页 教学要求 ⚫ 通过本单元学习，了解、掌握有关图: –基本概念 •有向图、无向图、连通图、网 –存储结构及实现 •邻接矩阵、邻接表 –遍历及其它操作 •深度优先、广度优先遍历 –应用
本单元涉及的内容 ●第2章 2.5图的逻辑结构及其运算 2.6图类 27图的遍历 2.8树和图的基本应用 ●P73P90 □上一页 停止放映 第4页
下一页 上一页 停止放映 第 4 页 本单元涉及的内容 ⚫ 第2章 – 2.5图的逻辑结构及其运算 – 2.6图类 – 2.7图的遍历 – 2.8树和图的基本应用 ⚫ P73~P90
、图及其基本概念 ●图是一种较之线性表和树形结构更为复杂 的非线性数据结构。图中各数据元素之间 的关系可以是任意的,描述的是“多对多” 的关系。 图的定义 有向图、无向图 图的基本概念 邻接点、顶点、边、弧、顶点的度 □上一页 连通图、强连通图、连通分量 停止放映 网、权 第5页
下一页 上一页 停止放映 第 5 页 一、图及其基本概念 ⚫ 图是一种较之线性表和树形结构更为复杂 的非线性数据结构。图中各数据元素之间 的关系可以是任意的，描述的是“多对多” 的关系。 –图的定义 • 有向图、无向图 –图的基本概念 • 邻接点、顶点、边、弧、顶点的度 • 连通图、强连通图、连通分量 • 网、权
图结构 ●图是对结点的前趋和后继个数不加限制的 数据结构。有关图的理论,在“离散数学” 的图论中有详细论述和证明。在DS中,只 讨论图在计算机中的实现和操作。 现实生活中,图的应用范围很广泛,涉及 电讯工程、电网调度、集成电路设计 交通管理、工程管理、系统工程等领域 □上一页 停止放映 第6页
下一页 上一页 停止放映 第 6 页 图结构 ⚫ 图是对结点的前趋和后继个数不加限制的 数据结构。有关图的理论，在“离散数学” 的图论中有详细论述和证明。在DS中，只 讨论图在计算机中的实现和操作。 ⚫ 现实生活中，图的应用范围很广泛，涉及： –电讯工程、电网调度、集成电路设计 –交通管理、工程管理、系统工程等领域
图( Graph)的定义 图G=(V,E) 其中:V={v1,v2,……,m}是非空有穷的结 点集合;E是顶点偶对的集合。 ●例,图G1=(V,E) V={v1,v2,w3,v4} E={(v1,v2),(v1,v3) 2 (v2,v1),(v2,v3) (v2,V4),(v3,v1) □上一页 (v3,v2),(v4,v2) 停止放映 3 G1 第7页
下一页 上一页 停止放映 第 7 页 图（Graph）的定义 ⚫ 图G = （V，E ） 其中： V={ v1，v2，……,vn}是非空有穷的结 点集合;E 是顶点偶对的集合。 ⚫ 例，图G1 = （V，E） V={v1，v2，v3，v4} E={（v1，v2），（v1，v3）， （v2，v1），（v2，v3）， （v2，v4），（v3，v1）， （v3，v2），（v4，v2） } o o o o v1 v2 v3 v4 G1
有向图、无向图 ●有向图( Digraph) 图G中顶点的偶对若是有向的,形成的图称有向 图。如图G2所示。 为示区别,其偶对用表示。 ●无向图( undigraph) 图G中顶点的偶对若是无向的,形成的图称为无 向图,其偶对用(x,wy)表示,如图G1所 G2=(V,E) □上一页 V={1,2,3,4} 停止放映 E={(1,2〉,〈1,3 G2 ,(3,4〉,〈4,1〉 第8页
下一页 上一页 停止放映 第 8 页 有向图、无向图 ⚫ 有向图（Digraph） 图G中顶点的偶对若是有向的，形成的图称有向 图。如图G2所示。 为示区别，其偶对用表示。 ⚫ 无向图（Undigraph） 图G中顶点的偶对若是无向的，形成的图称为无 向图，其偶对用（vx，vy）表示，如图G1所示。 ⚫ G2=（V，E） V={ 1，2，3，4} E={〈1，2〉，〈1，3〉 ，〈3，4〉，〈4，1〉} 1 3 2 4 G2
边、弧 边(Eage) 顶点间的关系可描述为顶点的偶对,也称为顶点的边。 记为:(Vx,Vy)。边是无序的,可以看成是(Wx, Vy),也可以看成是(Wy,Wx)。 弧(Arc) 若顶点间的边是有方向性(有序)的,则称该偶对为弧。 记为:〈Wx,Vy〉。弧是有序的,〈Wx,Wy〉表示从 Vx到Vy 弧头(Head) 弧的终点( Terminal node)称为弧头(方向前方)。 尾(ai1) □上一页 弧的起始点( Initial Node)称为弧尾(方向后方)。 停止放映 弧〈Vx,Wy)表示为, V Vy 弧尾 弧头 第9页
下一页 上一页 停止放映 第 9 页 边、弧 ⚫ 边（Edge） 顶点间的关系可描述为顶点的偶对，也称为顶点的边。 记为： （Vx，Vy）。边是无序的，可以看成是（Vx， Vy），也可以看成是（Vy，Vx）。 ⚫ 弧（Arc） 若顶点间的边是有方向性（有序）的，则称该偶对为弧。 记为：〈Vx，Vy〉。弧是有序的，〈Vx，Vy〉表示从 Vx到Vy。 ⚫ 弧头（Head） 弧的终点（TerminaL Node）称为弧头（方向前方）。 ⚫ 弧尾（Tail） 弧的起始点（Initial Node）称为弧尾（方向后方）。 弧 〈Vx，Vy〉表示为， Vx Vy 弧尾 弧头
顶点、邻接点 顶点( Vertex)图中的数据元素(结点)称为顶点。 如图G1、G2中的ⅴ1、V2,1,2 ●邻接点( Adjacent) 无向图中,若边(Vx,Vy)∈E, 则ⅴx、Vy互为邻接点。 有向图中,若弧〈Vx,Vy〉∈E, 则Vy是Vx的邻接点,反之,不是。 v2 Vx、Vy互为邻接点 □上一页 G2 停止放映 Vy是Vx的邻接点 V3 GI 4 第10页
下一页 上一页 停止放映 第 10 页 顶点、邻接点 ⚫ 顶点（Vertex） 图中的数据元素（结点）称为顶点。 如图G1、G2中的Ｖ1、Ｖ2，1，2。 ⚫ 邻接点（Adjacent） –无向图中，若边（Ｖx，Ｖy） E， 则Ｖx、Ｖy互为邻接点。 –有向图中，若弧〈Ｖx，Ｖy〉 E， 则Ｖy是Ｖx的邻接点，反之，不是。 Vx Vy Ｖx、Ｖy互为邻接点 Vx Vy Ｖy是Ｖx的邻接点 1 3 2 4 G2 o o o o v1 v2 v3 v4 G1
