数据结构38-图的定义与术语.ppt

1、数 据 结 构第三十八课 图的定义与术语,第三十课 图的定义与术语,本课主题： 图的定义与术语 教学目的： 掌握图的定义及常用术语 教学重点： 图的常用术语 教学难点： 图的常用术语 授课内容：,一、图的定义,图是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的抽象数据类型。,图的抽象数据类型定义(1),ADT Graph 数据对象V ：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R=VR VR=|v,wV且P(v,w),表示从v到w的弧， 谓词P(v,w)定义了弧的意义或信息 基本操作P： CreateGraph( 初始条件：V是图的顶点集，VR是图中弧的集合。

2、操作结果：按V和VR的定义构造图G,图的抽象数据类型定义(2),DestroyGraph( 初始条件：图G存在，v是G中某个顶点 操作结果：返回v的值。,FirstAdjVex(G,v); 初始条件：图G存在，v是G中某个顶点 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接 顶点，则返回“空” PutVex( 初始条件：图G存在,v是G中某个顶点,w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的 最后一个邻接点，则返回“空”,图的抽象数据类型定义(3),InsertVex( 初始条件：图G存在，v和w是G中两个顶点 操作结果：在G中增添弧,若G是无向的，则

3、还增添对称弧,图的抽象数据类型定义(4),DeleteArc( 初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函 数 操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次。一旦Visit()失败，则操作失败。,图的抽象数据类型定义(5),BFSTRaverse(G,v,Visit(); 初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数 操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次。一旦Visit()失败，则操作失败。 ADT Graph,图的抽象数据类型定义(6),二、图的常用术语(1),有向图、无向图 弧：; 边

4、(x,y)。,二、图的常用术语(2),对于无向图，e的取值范围是0到n(n-1)/2, 有n(n-1)/2条边的无向图称为无向完全图。,如果用n表示图中顶点数目，用e表示边或弧的数目， 则有：,二、图的常用术语(3),对于有向图，e有取值范围是0到n(n-1)。 具有n(n-1)条弧的有向图称为有向完全图。,二、图的常用术语(4),有很少条边或弧的图称为稀疏图，反之称为稠密图。,二、图的常用术语(5),和边（弧）相关的数叫权 带权的图称网。 邻接、邻接点 无向图中, 一条边连起来的两个顶点，互称邻接点； 有向图中,若从顶点x到顶点y有一条弧，则说顶点x邻接到顶点y，而顶点y邻接自顶点x。,对上

5、图有：G1=(V1,A1) 其中：V1=v1,v2,v3,v4 A1=,二、图的常用术语(6),二、图的常用术语(7),度、出度、入度 无向图中和顶点相关的边(e)的个数叫顶点的度。 有向图中从顶点出发的弧的个数叫该顶点的出度，入到该顶点的弧的个数叫该顶点的入度。TD(v)=ID(v)+OD(v),二、图的常用术语(8),路径、路径长度、回路(环)、简单路径 连通、连通图、连通分量 无向图顶点v1到顶点v2有路径，则说v1和v2连通。若任意两个顶点都连通，则说该图是连通的。连通分量是无向图中的极大连通子图。 强连通图、强连通分量,二、图的常用术语(9),二、图的常用术语(10),对有向图，如果每一对顶点之间都有通路，则称该图 为强连通图。,二、图的常用术语(11),生成树、有向树、生成森林 一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但只有足以构成一棵树的n-1条边。 若有向图中只有一个顶点的入度为0，其余顶点的入度均为1，则该有向图称为有向