西安交通大学：《计算机软件基础》第5单元 非线性数据结构

第5单元 非线性数据结构 图 计算机软件基础 The software bas ic of computer 主讲:赵英良 西安交通大学 计算机教学实验中心

下一页 计算机软件基础 The software basic of computer 主讲：赵英良 西安交通大学 计算机教学实验中心 第5单元 非线性数据结构 图

上节内容提要 1.树的定义 2.树的基本概念 结点、结点度、根、支、叶结点 子结点、父结点、兄弟结点 树的度、路径、长度、深度 森林、有序、无序 停止放映 下一页 第2页

下一页 上一页 停止放映 第 2 页 上节内容提要 1.树的定义 2.树的基本概念 结点、结点度、根、支、叶结点 子结点、父结点、兄弟结点 树的度、路径、长度、深度 森林、有序、无序

上节内容提要 B.二叉树 二叉树的定义 二叉树的性质(每层结点个数、总结点数) 二叉树的存储结构:顺序存储、记录数组结构(结点、左 子、右子)、链式存储结构(二叉链表三叉链表) 特殊二叉树 满二叉树(性质)、完全二叉树(性质)、平衡二叉树、 二叉排序树) 二叉树的遍历操作(前序、中序、后序) 树的存储结构 数组实现方法(双亲表示法)、链表实现方式(孩子表 停止放映 示法)、二叉链表实现方式(孩子兄弟表示法) }.树、森林与二叉树的转换 第3页

下一页 上一页 停止放映 第 3 页 上节内容提要 3.二叉树 二叉树的定义 二叉树的性质（每层结点个数、总结点数） 二叉树的存储结构:顺序存储、记录数组结构(结点、左 子、右子)、链式存储结构（二叉链表三叉链表） 4.特殊二叉树 满二叉树（性质）、完全二叉树（性质）、平衡二叉树、 二叉排序树） 5.二叉树的遍历操作（前序、中序、后序） 6.树的存储结构: 数组实现方法（双亲表示法）、链表实现方式（孩子表 示法）、二叉链表实现方式（孩子兄弟表示法） 7.树、森林与二叉树的转换

第5单元 线性数据结构

下一页 第5单元 非线性数据结构 图

图及其基本概念 ●图是一种较之线性表和树形结构更为复杂 的非线性数据结构。图中各数据元素之间 的关系可以是任意的,描述的是“多对多” 的关系。 ●图是对结点的前趋和后继个数不加限制的 数据结构。 停止放映 下一页 第5页

下一页 上一页 停止放映 第 5 页 一、图及其基本概念 ⚫ 图是一种较之线性表和树形结构更为复杂 的非线性数据结构。图中各数据元素之间 的关系可以是任意的，描述的是“多对多” 的关系。 ⚫ 图是对结点的前趋和后继个数不加限制的 数据结构

图( Graph)的定义 ●图G=(V,E) 其中:V={v,v2,……,vn}是非空有穷的 结点集合;E是顶点偶对的集合。 ●例,图G1=(V,E) {v1,v2,v3,ⅴ4} E={(v1,v2),(v1,v3),v1 2 (v2,v1),(v2,v3) (v2,V4),(v3,v1) (v3,V2),(v4,v2) 停止放映 3 下一页 GI 第6页

下一页 上一页 停止放映 第 6 页 图（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所示。 为示区别,其偶对用表示。 无向图( digraph) 图G中顶点的偶对若是无向的,形成的图称为无向 图,其偶对用(vx,w)表示区别在括号),如图G1 所示。 G2=(V,E) V={1,2,3,4 E={(1,2〉,(1,3〉 G2 停止放映 〈3,4〉,〈4,1〉} 下一页 第7页

下一页 上一页 停止放映 第 7 页 有向图、无向图 ⚫ 有向图（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

边、弧 边(Buge) 顶点间的关系可描述为顶点的偶对,也称为顶点的边。 记为:(Wx,Wy)。边是无序的,可以看成是(Vx, Vy),也可以看成是(Vy,Wx)。 弧(Arc) 若顶点间的边是有方向性(有序)的,则称该偶对为弧。 记为:〈Wx,Vy〉。弧是有序的,〈Wx,Vy〉表示从 Vx到Vy 弧头(Head) 弧的终点( Terminal Node)称为弧头(方向前方)。 弧尾(7ai1) 弧的起始点( Initial Node)称为弧尾(方向后方)。 停止放映 弧〈Vx,Wy)表示为, VX 下一页 弧尾 弧头 第8页

下一页 上一页 停止放映 第 8 页 边、弧 ⚫ 边（Edge） 顶点间的关系可描述为顶点的偶对，也称为顶点的边。 记为： （Vx，Vy）。边是无序的，可以看成是（Vx， Vy），也可以看成是（Vy，Vx）。 ⚫ 弧（Arc） 若顶点间的边是有方向性（有序）的，则称该偶对为弧。 记为：〈Vx，Vy〉。弧是有序的，〈Vx，Vy〉表示从 Vx到Vy。 ⚫ 弧头（Head） 弧的终点（TerminaL Node）称为弧头（方向前方）。 ⚫ 弧尾（Tail） 弧的起始点（Initial Node）称为弧尾（方向后方）。 弧 〈Vx，Vy〉表示为， Vx Vy 弧尾 弧头

顶点、邻接点 顶点( ertex):图中的数据元素(结点)称为顶点。 如图G1、G2中的V1、V2,1,2 邻接点( Adjacent) 无向图中,若边(Vx,Vy)∈E, 则ⅴx、Vy互为邻接点。 有向图中,若弧〈Vx,Vy〉∈E, 则ⅴy是Vx的邻接点,反之,不是。(弧头是弧尾的邻接点 2 Vx、Vy互为邻接点 停止放映 下一页 V3 GI 0y4Vy是vx的邻接点 第9页

下一页 上一页 停止放映 第 9 页 顶点、邻接点 ⚫ 顶点（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

顶点的度( Degree) 无向图中,顶点的度是以该顶点为一个端点的边 的条数。例如,G1中V2的度为3,V4的度为1。 有向图中,以某顶点为弧头的弧的数目称为该顶 点的入度( Indegree)。例如G中顶点1的入度 为1。以某顶点为弧尾的弧的数目称为该顶点的 出度(0 utdegree)。例如G2中顶点1的出度为2。 该顶点的度=入度+出度。例如,G2中顶点1的度 =2+1=3。 V 0 V2 G1 G2 停止放映 下一页 v4 第10页

下一页 上一页 停止放映 第 10 页 顶点的度（Degree） ⚫ 无向图中，顶点的度是以该顶点为一个端点的边 的条数。例如，G1中V2的度为3，V4的度为1。 ⚫ 有向图中，以某顶点为弧头的弧的数目称为该顶 点的入度（Indegree）。例如G2中顶点1的入度 为1。以某顶点为弧尾的弧的数目称为该顶点的 出度（Outdegree）。例如G2中顶点1的出度为2。 该顶点的度=入度+出度。例如，G2中顶点1的度 =2+1=3。 o o o o v1 v2 v3 v4 G1 1 3 2 4 G2