数据结构图及其存储结构

《数据结构图及其存储结构》由会员分享，可在线阅读，更多相关《数据结构图及其存储结构（21页珍藏版）》请在装配图网上搜索。

1、图及其存储结构11.1.图图的有关概念的有关概念 图图(Graph)的的ADT定义：定义：图图是是n(n0 0)个结点的有限集合。个结点的有限集合。在任意一个图中任意两个结点之间都可能相关。图的在任意一个图中任意两个结点之间都可能相关。图的ADT定义如下：定义如下：一、基本概念一、基本概念数据对象数据对象V：V是具有相同特性的数据元素的集合，并称为顶点集是具有相同特性的数据元素的集合，并称为顶点集合。合。数据关系数据关系R：R=E E=|v,wV,且有谓词且有谓词P(v,w),表示从表示从v到到w的的弧，谓词弧，谓词P(v,w)定义了弧定义了弧上的信息或权值上的信息或权值基本操作基本操作P：详

2、见详见P.156。图的二元组表示：图的二元组表示：G=(V，E)E即为图中边或弧的集合。即为图中边或弧的集合。21.1.图图的有关概念的有关概念 图的有关术语：图的有关术语：一、基本概念一、基本概念 图中的数据元素称为图中的数据元素称为顶点；顶点；有向图；有向图；弧；弧；弧头；弧头；弧尾；弧尾；无向图；无向图；边；边；*定理定理：若用：若用e表示有向图或无向图中弧或边的条数，表示有向图或无向图中弧或边的条数，即即e=|E|,则有：则有：在有向图中：在有向图中：0en(n-1)在无向图中：在无向图中：0en(n-1)/2 具有具有n(n-1)/2条边的无向图称为条边的无向图称为完全图：完全图：具

3、有具有n(n-1)条边的有向图称为条边的有向图称为有向完全图：有向完全图：v1v2v3v4012331.1.图图的有关概念的有关概念 图的有关术语：图的有关术语：一、基本概念一、基本概念顶点的度；顶点的度；有向图中顶点的度有向图中顶点的度是该顶点的入度与出度之和。是该顶点的入度与出度之和。无向图中顶点的度无向图中顶点的度是与该顶点相关联的边的条数。是与该顶点相关联的边的条数。子图：子图：对于对于G1=(V1,E1),G2=(V2,E2),若若V2 V1，E2 E1，则，则称称G2是是G1的子图。的子图。回路（环）：回路（环）：若一条路径上的顶点均不相同则该路径称若一条路径上的顶点均不相同则该路

4、径称为为简单路径简单路径；除了顶点和终点相同外，路径上的其他顶；除了顶点和终点相同外，路径上的其他顶点均不相同的路径称为点均不相同的路径称为回路回路或或环环。v1v2v3v4012341.1.图图的有关概念的有关概念 图的有关术语：图的有关术语：一、基本概念一、基本概念 无向图中任意两个顶点都是连通的，则该图为无向图中任意两个顶点都是连通的，则该图为连通图连通图。有向图中任何有序顶点对之间都有有向路径，则称该图是有向图中任何有序顶点对之间都有有向路径，则称该图是强连通的强连通的。无向图中最大的连通子图称为该图的。无向图中最大的连通子图称为该图的连通分支连通分支；有向图中相应地称为有向图中相应地

5、称为强连通分支强连通分支。v1v2v3v4012351.1.图图的有关概念的有关概念 图的有关术语：图的有关术语：一、基本概念一、基本概念 一个连通无向图的一个连通无向图的生成树生成树是该图的一个连通分量，它是该图的一个连通分量，它包含有该图的所有包含有该图的所有n个顶点以及连接这个顶点以及连接这n个顶点的（个顶点的（n-1）条边。条边。边或弧上带权值的图称为边或弧上带权值的图称为带权图带权图或或网网（分为（分为无向网无向网和和有向网有向网）。）。一个无向图的所有生成树中，边上的权值之和最小的一个无向图的所有生成树中，边上的权值之和最小的生成树称为该图的生成树称为该图的最小生成树最小生成树或或

6、最小代价生成树最小代价生成树。v1v2v3v4v5v6655125646361.1.图图的有关概念的有关概念 图的有关术语：图的有关术语：一、基本概念一、基本概念图中顶点的图中顶点的“序号序号”及其邻接点的及其邻接点的“序号序号”：由于图中顶点之间不存在全序关系，所以无法将图中由于图中顶点之间不存在全序关系，所以无法将图中顶点进行线性排序。但为了实现图的存储结构，我们必须顶点进行线性排序。但为了实现图的存储结构，我们必须给每个顶点附加一个人为规定的给每个顶点附加一个人为规定的“序号序号”。这个序号即称。这个序号即称为该为该顶点在图中的位置顶点在图中的位置。对于任意一个顶点而言，若它有两个以上的

7、邻接点，对于任意一个顶点而言，若它有两个以上的邻接点，则它的邻接点也有所谓则它的邻接点也有所谓“第一个邻接点第一个邻接点”，“第二个邻第二个邻接点接点”，.，这个顺序也称为，这个顺序也称为邻接顺序邻接顺序。72.2.图图的遍历的遍历 一、基本概念一、基本概念图的遍历图的遍历：从图中某一顶点出发按一定规律沿着图中的边：从图中某一顶点出发按一定规律沿着图中的边或弧访问每一顶点一次且仅一次的操作称为对图的遍历。或弧访问每一顶点一次且仅一次的操作称为对图的遍历。*图的遍历有两种方法：图的遍历有两种方法：深度优先遍历深度优先遍历和和广度优先遍历广度优先遍历 *若图是连通的或是强连通的，则遍历过程所经过的

8、边若图是连通的或是强连通的，则遍历过程所经过的边（或弧）加上图中所有顶点就是图的一棵（或弧）加上图中所有顶点就是图的一棵生成树生成树。*对于不连通图而言，从某一连通分支中的某一顶点出对于不连通图而言，从某一连通分支中的某一顶点出发执行一次发执行一次“遍历遍历”算法可得该连通分支的算法可得该连通分支的生成子树生成子树。若。若干次使用上述方法可得图的干次使用上述方法可得图的生成森林生成森林。81.1.图图的数组表示法的数组表示法 二、存储结构二、存储结构*思想思想：用两个数组分别存储数据元素：用两个数组分别存储数据元素(顶点顶点)的信息和数据元素之间的关系：即用一个一的信息和数据元素之间的关系：即

9、用一个一维数组维数组vexs存放各顶点的有关信息；用一个存放各顶点的有关信息；用一个二维数组二维数组arcs存放各条边或弧的有关信息存放各条边或弧的有关信息（如存放边或弧上的权值）。（如存放边或弧上的权值）。91.1.图图的数组表示法的数组表示法 二、存储结构二、存储结构#define INFINITY INT_MAX /用以表示用以表示#define MAX_VERTEX_NUM 20 /最大顶点数最大顶点数typedef enum DG,DN,UDG,UDN GraphKind;/有向图有向图,有向网有向网,无向图无向图,无向网无向网typedef struct ArcCell VRTyp

10、e adj;/VRType是顶点关系类型，对无权图，用是顶点关系类型，对无权图，用0或或1表示表示 /相邻否；对带权图，则为权值类型（如整型）相邻否；对带权图，则为权值类型（如整型）InfoType *info;/该弧相关信息存放位置指针该弧相关信息存放位置指针 ArcCell,AdiMatrix MAX_VERTEX_NUM,MAX_VERTEX_NUM;/AdiMatrix为一个数组元素类型为为一个数组元素类型为ArcCell的的二维数组二维数组typedef struct VertexType vexs MAX_VERTEX_NUM ;/一维数组存放顶点的信息一维数组存放顶点的信息 Ad

11、jMatrix arcs;/二维数组存放边或弧上的信息（如权值）二维数组存放边或弧上的信息（如权值）int vexnum,arcnum;/分别存放图的顶点数目和弧的条数分别存放图的顶点数目和弧的条数 GraphKind kind;/图的种类标志图的种类标志 MGraph101.1.图图的数组表示法的数组表示法 二、存储结构二、存储结构例1：例如：例如：MGraph G1;0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0G1.vexs0=v1，.，G1.vexs3=v4；G1.vexnum=4；G1.arcnum=4 ；G1.kind=DGG1.arcs=v1v2v3v401231

12、11.1.图图的数组表示法的数组表示法 二、存储结构二、存储结构例2：v1v2v4v50134v32MGraph G2;0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0G2.vexs0=v1，.，G2.vexs4=v5；G2.vexnum=5；G2.arcnum=6 ；G2.kind=UDGG2.arcs=122.2.数组表示法前提下数组表示法前提下图的输入图的输入 二、存储结构二、存储结构*当输入一个图时，要求用户先输入图的类型：Status CreateGraph(MGraph&G)cinG.kind;switch(G.kind)case

13、DG:return CreateDG(G);case DN:return CreateDN(G);case UDG:return CreateUDG(G);case UDN:return CreateUDN(G);default:return ERROR;/CreateGraph13二、存储结构二、存储结构*以无向网为例,即当用户输入图的类型标志为UDN时,有：Status CreateUDN(MGraph&G)scanf(G.vexnum,G.arcnum,IncInfo);/IncInfo 为0时表示各弧 /不含其他信息 for(i=0;iG.vexnum;+i)scanf(G.vexsi

14、);/一维数组存放顶点值 for(i=0;iG.vexnum;+i)/二维数组赋初值 for(j=0;jG.vexnum;+j)G.arcsij=,NULL;/Arccell的形式为:for(k=0;kG.kind;switch(G.kind)case 0:return CreateAL0(G);case 1:return CreateAL1(G);case 2:return CreateAL2(G);case 3:return CreateAL3(G);default:return ERROR;/CreateGraph18二、存储结构二、存储结构4.4.邻接表表示法前提下图的输入邻接表表示法

15、前提下图的输入 *以无向图为例,即当用户输入图的类型标志为2时,有：Status CreateAL2(ALGraph&G)scanf(G.vexnum,G.arcnum);/输入顶点数和弧的条数 n=G.vexnum;e=G.arcnum;G.kind=2;for(i=0;in;+i)scanf(G.verticesi.data);G.verticesi.firstarc=NULL;/输入顶点vi的值 for(k=1;kadjvex=j;p-nextarc=G.verticei.firstarc;G.verticei.firstarc=p;p=new Arcnode;/由于边可视为对称的两条弧，故再申请一个表头结 /点存放序号i,并将其插入到vj的单链表中 p-adjvex=i;p-nextarc=G.verticej.firstarc;G.verticej.firstarc=p;return OK;/CreateAL2v1v2v4v50134v32例如：19二、存储结构二、存储结构4.4.邻接表表示法前提下图的输入邻接表表示法前提下图的输入 v1v2v4v50134v32v1310v24210v34321v4203v5214例如：20End21