资源描述：
《数据结构38-图的定义与术语》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构第三十八课图的定义与术语第三十课图的定义与术语本课主题：图的定义与术语教学目的：掌握图的定义及常用术语教学重点：图的常用术语教学难点：图的常用术语授课内容：一、图的定义图是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的抽象数据类型。图的抽象数据类型定义(1)ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={
2、v,w∈V且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作P
3、：CreateGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G图的抽象数据类型定义(2)DestroyGraph(&G);初始条件：图G存在 操作结果：销毁图GLocateVex(G,u);初始条件：图G存在，u一G中顶点有相同特征操作结果：若G中存在顶点u,则返回该顶点在图中位置；否则返回其它信息。GetVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的值。FirstAdjVex(G,v);初始条件：图G存在，v是G中某个
4、顶点操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”PutVex(&G,v,value);初始条件：图G存在，v是G中某个顶点操作结果：对v赋值valueNextAdjVex(G,v,w);初始条件：图G存在,v是G中某个顶点,w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”图的抽象数据类型定义(3)InsertVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征操作结果：在图G中增添新顶点vDeleteVex(&G,
5、v);初始条件：图G存在，v是G中某个顶点操作结果：删除G中顶点v及其相关的弧InsertAcr(&G,v,w);初始条件：图G存在，v和w是G中两个顶点操作结果：在G中增添弧,若G是无向的，则还增添对称弧图的抽象数据类型定义(4)DeleteArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点操作结果：在G中删除弧,若G是无向的，则还删除对称弧DFSTraverser(G,v,Visit());初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用
6、函数操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次。一旦Visit()失败，则操作失败。图的抽象数据类型定义(5)BFSTRaverse(G,v,Visit());初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次。一旦Visit()失败，则操作失败。}ADTGraph图的抽象数据类型定义(6)二、图的常用术语(1)有向图、无向图弧：;边(x,y)。二、图的常用术语(2)对于无向图，e的
7、取值范围是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。对
8、上图有：G1=(V1,{A1})其中：V1={v1,v2,v3,v4} A1={,,,}二、图的常用术语(6)二、图的常用术语(7)度、出度、入度无向图中和顶点相关的边(e)的个数叫顶点的度。有向图中从顶点出发的弧的个数叫该顶点的出度，入到该顶点的弧的个数叫该顶点的入度。TD(v)=ID(v)+OD(v)二、图的常用术语(8)路径、路径长度、回路(环)、简单路径连通、连通图、连通分量无向图顶点v1到顶点v2有路径，则说v1和v2连通。若任意两个顶点都连
9、通，则说该图是连通的。连通分量是无向图中的极大连通子图。强连通图、强连通分量二、图的常用术语(9)二、图的常用术语(10)对有向图，如果每一对顶点之间都有通路，则称该图为强连通图。二、图的常用术语(11)生成树、有向树、生成森林一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但只有足以构成一棵树的n-1条边。若有向图中只有一个顶点的入度为0，其余顶点的入度均为1，则该有向图称为有向树。有向图的生成森林由
