数据结构-图课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构-图课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件
- 资源描述:
-
1、5.1 图的基本概念图的基本概念 图是一种重要的,比树更复杂的非线性数据结构。图是一种重要的,比树更复杂的非线性数据结构。在树中,每个结点只与上层的父结点有联系,并在树中,每个结点只与上层的父结点有联系,并可以与其下层的多个子结点有联系。但在图中,可以与其下层的多个子结点有联系。但在图中,结点之间的联系是任意的,每个结点都可以与其结点之间的联系是任意的,每个结点都可以与其它的结点相联系。它的结点相联系。 图的应用极为广泛,特别是近年来发展迅速,已图的应用极为广泛,特别是近年来发展迅速,已渗入到诸如语言学、逻辑学、物理、化学、电信渗入到诸如语言学、逻辑学、物理、化学、电信工程、计算机、数学及其它
2、分支中。工程、计算机、数学及其它分支中。图的定义及相关术语图的定义及相关术语(1)图的定义:图的定义:图图G由两个集合由两个集合V(G)和和E(G)所所组成组成,记作,记作G=(V,E)。其中,。其中,V(G)是图中顶是图中顶点的非空有限集合,点的非空有限集合,E(G)是图中边的有限是图中边的有限集合。集合。 (2) 有向图有向图。如果图中每条边都是顶点的有序。如果图中每条边都是顶点的有序对,即每条边都用箭头表明了方向,则此对,即每条边都用箭头表明了方向,则此图为有向图。有向图中的图为有向图。有向图中的边也称为弧边也称为弧,用,用尖括号尖括号括起一对顶点表示。括起一对顶点表示。有向图示例有向图
3、示例1324G1 图中所示的图中所示的G1为有向图,它由为有向图,它由V(G1)和和E(G1)组成。组成。 V(G1)= V1,V2,V3,V4 E(G1)= , 如其中弧如其中弧,称,称V1为初始点或弧之为初始点或弧之尾,尾,V2为终端点或弧之头。为终端点或弧之头。 (3) 无向图无向图。如果图中每条边都是顶点的无。如果图中每条边都是顶点的无序对,则称此图为无向图。无向边用序对,则称此图为无向图。无向边用圆括号圆括号括起的两个相关顶点来表示。如图所示的括起的两个相关顶点来表示。如图所示的G2为无向图。为无向图。 V(G2)= V1,V2,V3,V4 E(G2)= (V1, V2),(V1,
4、V3),(V3, V4),( V4, V1) 注意,在无向图中,注意,在无向图中,(V1, V2)与与(V2, V1)表示表示同一条边。同一条边。图图3-23 无向图示例无向图示例1234G2 (4) 子图子图。设有两个图。设有两个图GA和和GB,且满足,且满足 V(GB) V(GA) E(GB) E(GA) 则称则称GB是是GA的子图。如下图所示。的子图。如下图所示。132112132132G3G3的子图 图与子图图与子图 (5) 带权图带权图。在图的边或弧上加上一个相关。在图的边或弧上加上一个相关联的数联的数(权权),称为带权图或网。如下图所示。,称为带权图或网。如下图所示。ABECF15
5、97211132有向网有向网14235915251030无向网无向网(6)完全图完全图。假设图中有假设图中有 n 个顶点,个顶点,e 条条边,则含有边,则含有 e=n(n-1)/2 条边的无向图称条边的无向图称作作完全图完全图;含有含有 e=n(n-1) 条弧的有向图条弧的有向图称作称作有向完全图。有向完全图。(7) 稠密图与稀疏图稠密图与稀疏图。若图的边或弧的数若图的边或弧的数目接近于相应完全图的边或弧的数目,目接近于相应完全图的边或弧的数目,则称之为则称之为稠密图稠密图,否则称为,否则称为稀疏图。稀疏图。 (8) 路径路径。在一个图中,如果从顶点。在一个图中,如果从顶点V1出发,出发,沿着
6、一些边经过顶点沿着一些边经过顶点V1,V2,Vn-1到达到达顶点顶点Vn,则称顶点序列,则称顶点序列(V1,V2,Vn-1 ,Vn)为从为从V1到到Vn的一条路径。的一条路径。路径上边路径上边(弧弧)的数目称为该路径的长度的数目称为该路径的长度。例如:下图中,例如:下图中,A,B,C,F的路径长度为的路径长度为3。ABECF(9) 简单路径简单路径:序列中顶点不重复出现的路径。:序列中顶点不重复出现的路径。(10) 简单回路简单回路:序列中第一个顶点和最后一:序列中第一个顶点和最后一个顶点相同的简单路径。个顶点相同的简单路径。(11) 连通图:连通图:在无向图中,若每一对顶点之在无向图中,若每
7、一对顶点之间都有路径,则称此图为间都有路径,则称此图为连通图连通图。(12) 连通分量:连通分量:若无向图为非连通图,则图若无向图为非连通图,则图中各个极大连通子图称作此图的中各个极大连通子图称作此图的连通分量连通分量。连通图连通图BACDFEBACDFE非连通图非连通图(13) 强连通图:强连通图:在有向图中,若每一对顶点在有向图中,若每一对顶点u和和v之间都存在之间都存在v到到u及及u到到v的路径,则称此的路径,则称此图为图为强连通图强连通图。(14) 强连通分量:强连通分量:各个强连通子图称作该各个强连通子图称作该有有向图向图的的强连通分量强连通分量。强连通图强连通图ABECFABECF
8、非强连通图非强连通图(15) 邻接点邻接点。在无向图中,如果边。在无向图中,如果边 (u,v)E,则,则u和和v互为邻结点,即互为邻结点,即u是是v的邻结点,的邻结点,v也是也是u的的邻结点。邻结点。边边(v,w) 与顶点与顶点u 和和v相相关联关联。在有向图中,如果弧在有向图中,如果弧E,则,则v是是u的邻结的邻结点。称点。称u邻接到邻接到v,或顶点,或顶点v邻接自顶点邻接自顶点u。(16) 顶点的度顶点的度。在无向图中,顶点的度就是和该。在无向图中,顶点的度就是和该顶点相关联的边的数目,记为顶点相关联的边的数目,记为TD(V)。在有向图。在有向图中,以某顶点为弧头的弧的数目,称为此顶点中,
9、以某顶点为弧头的弧的数目,称为此顶点的的入度入度,记作,记作ID(V);以某顶点为弧尾的弧的数;以某顶点为弧尾的弧的数目称为此顶点的目称为此顶点的出度出度,记作,记作OD(V)。该顶点的度。该顶点的度则是此顶点的入度与出度之和。则是此顶点的入度与出度之和。ACDFETD(B) = 3,TD(A) = 2 BABECFID(B) = 2,OD(B) = 1TD(B)=ID(B)+OD(B) =3建立和销毁图结构建立和销毁图结构插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作访问顶点访问顶点遍历图遍历图插入和删除弧插入和删除弧基本操作基本操作5.2 图的存储结构图的存储结构图的存储结构图的
10、存储结构一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示二、图的邻接表存储表示二、图的邻接表存储表示*三、有向图的十字链表存储表示三、有向图的十字链表存储表示 *四、无向图的邻接多重表存储表示四、无向图的邻接多重表存储表示根据图的定义可知,一个图的逻辑结构分两部根据图的定义可知,一个图的逻辑结构分两部分,一部分是组成图的分,一部分是组成图的顶点的集合顶点的集合;另一部分;另一部分是顶点之间的联系,即是顶点之间的联系,即边或弧的集合边或弧的集合。可用一个一维数组存放图中所有顶点的信息;可用一个一维数组存放图中所有顶点的信息;用一个二维数组来存放数据元素之间的关系的用一个二维数组来存放
11、数据元素之间的关系的信息信息(即边或弧的集合即边或弧的集合E)。这个二维数组称之为。这个二维数组称之为邻接矩阵。邻接矩阵。邻接矩阵是表示顶点之间的邻接关系的矩阵邻接矩阵是表示顶点之间的邻接关系的矩阵。设设G =(V,E)是有是有n(n1)个顶点的图,则个顶点的图,则G的邻的邻接矩阵接矩阵A是一个是一个nn阶矩阵。阶矩阵。Aij=0 若(Vi,Vj)或E(G)1 若(Vi,Vj)或E(G)一、图的数组一、图的数组( (邻接矩阵邻接矩阵) )存储表示存储表示定义定义:矩阵的元素为矩阵的元素为BADFEC010010100011000101001001110000011100ABCDEFABCDEF
12、有向图的邻接矩阵有向图的邻接矩阵ABDCE0101000100000010010011000ABCDE 在一般情况下,我们不关心图中顶点在一般情况下,我们不关心图中顶点的情况,若将顶点编号为的情况,若将顶点编号为1Vtxnum,设弧上或边上无权值,则图的存储结构设弧上或边上无权值,则图的存储结构可以简化为用一个二维数组表示:可以简化为用一个二维数组表示: int adjmatrixVtxnumVtxnum;无向图无向图的邻接矩阵是对称的的邻接矩阵是对称的; ; 有向图有向图的邻接矩阵不一定对称。的邻接矩阵不一定对称。对于无向图,邻接矩阵第对于无向图,邻接矩阵第i行行(或第或第i列列)的元的元素
13、之和是顶点素之和是顶点Vi的度。的度。对于有向图,邻接矩阵第对于有向图,邻接矩阵第i行元素之和为顶行元素之和为顶点点Vi的出度;第的出度;第i列的元素之和为顶点列的元素之和为顶点Vi的的入度。入度。使用邻接矩阵法容易使用邻接矩阵法容易判断任意两个点的邻判断任意两个点的邻接关系。接关系。 网的邻接矩阵可定义为网的邻接矩阵可定义为ijijijW (V, V) V, VE(G)Ai, j 反之若若或或其中其中Wij是边是边(Vi, Vj)或弧或弧上的权值。上的权值。 邻接表是一种顺序分配和链式分配相结合的邻接表是一种顺序分配和链式分配相结合的存储结构存储结构。它包括两个部分:一部分是。它包括两个部分
14、:一部分是链表链表;另一部分是另一部分是向量向量。 在邻接表中,对图中每个顶点建立一个单链在邻接表中,对图中每个顶点建立一个单链表,第表,第i个单链表中的结点包含了顶点个单链表中的结点包含了顶点Vi的所的所有邻接顶点。每个结点由三个域组成:有邻接顶点。每个结点由三个域组成:adjvex、data和和nextarc,如下图所示。,如下图所示。二、图的邻接表存储表示二、图的邻接表存储表示邻接表中表结点的结点结构邻接表中表结点的结点结构顶点顶点Vi的邻接点在图中的位置的邻接点在图中的位置指向顶点指向顶点Vi的下一邻接点的指针的下一邻接点的指针adjvexdatanextarc权值权值 为便于邻接表操
15、作,在每个单链表上附设一为便于邻接表操作,在每个单链表上附设一个头结点,在头结点中有两个域:个头结点,在头结点中有两个域:vexdata和和firstarc。如下图所示。如下图所示。邻接表中头结点的结点结构邻接表中头结点的结点结构 vexdatafirstarc指向顶点指向顶点Vi的第一个邻接点的指针的第一个邻接点的指针存储存储Vi的名字或有关信息的名字或有关信息 为了利用顺序存储结构的随机访问特性,邻为了利用顺序存储结构的随机访问特性,邻接表中将每个单链表的头结点以顺序结构的形接表中将每个单链表的头结点以顺序结构的形式存储,以便能随机访问任一顶点的单链表。式存储,以便能随机访问任一顶点的单链
16、表。 邻接表的存储结构可以用邻接表的存储结构可以用C语言描述如下:语言描述如下: #define VTXUNMn /*n为图中顶点个数的最大可能值为图中顶点个数的最大可能值*/ struct arcnode int adjvex;float data;struct arcnode *nextarc; ; typedef struct arcnode ARCNODE; struct headnode int vexdata;ARCNODE *firstarc; adjlistVTXUNM;BACDFE0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3 示
17、例:无向图的邻接表示例:无向图的邻接表有向图的邻接表有向图的邻接表ABDCE在有向图的邻接表中不在有向图的邻接表中不易找到指向该顶点的弧,易找到指向该顶点的弧,即难以确定某个顶点的即难以确定某个顶点的入度。入度。1 3242 00 1 2 3 4 A B C D E1ABECD有向图的逆邻接表有向图的逆邻接表在有向图的逆邻接表在有向图的逆邻接表中,每个顶点链接的中,每个顶点链接的是指向该顶点的弧。是指向该顶点的弧。A B C D E 303120 012344 有向带权图的邻接表有向带权图的邻接表231231437ABCABC734(a)(b) 在邻接表上容易找到任一顶点的第一个邻接在邻接表上
展开阅读全文