程序员人生 网站导航

数据结构 - 图的存储结构

栏目:数据库应用时间:2015-06-16 09:00:27

图的抽象数据类型定义

图是1种数据结构,加上1组基本操作就构成了图的抽象数据类型。 图的抽象数据类型定义以下: ADT Graph{ 数据对象V:具有相同特性的数据元素的集合,称为顶点集。 数据关系R:R={VR} VR={<v,w>|<v,w>| v,w?V∧p(v,w) ,<v,w>表示 从v到w的弧,P(v,w)定义了弧<v,w>的信息 }
基本操作PCreate_Graph() : 图的创建操作。 初始条件:无。 操作结果:生成1个没有顶点的空图G。GetVex(G, v) : 求图中的顶点v的值。 初始条件:图G存在,v是图中的1个顶点。 操作结果:生成1个没有顶点的空图G。 … … DFStraver(G,V):从v动身对图G深度优先遍历。 初始条件:图G存在。 操作结果:对图G深度优先遍历,每一个顶点访问且只访问1次。 ? ? BFStraver(G,V):从v动身对图G广度优先遍历。 初始条件:图G存在。 操作结果:对图G广度优先遍历,每一个顶点访问且只访问1次。 } ADT Graph

图的存储结构

  图的存储结构比较复杂,其复杂性主要表现在:

◆ 任意顶点之间可能存在联系,没法以数据元素在存储区中的物理位置来表示元素之间的关系,所以不能用简单的顺序存储结构来表示。
◆ 图中顶点的度不1样,有的可能相差很大,若按度数最大的顶点设计结构,则会浪费很多存储单元,反之按每一个顶点自己的度设计不同的结构,又会影响操作。
图的经常使用的存储结构有:邻接矩阵、邻接链表、10字链表、邻接多重表和边表。

邻接矩阵(数组)表示法

  图的邻接矩阵基本思想:用两个数组来表示图:1个1维数组存储顶点信息,1个2维数组存储边或弧的信息。该2维数组称为邻接矩阵。

无权图邻接矩阵的特点

无向图邻接矩阵的特性
邻接矩阵是对称方阵;
对顶点vi,其度数是第i行的非0元素的个数;
无向图的边数是上(或下)3角形矩阵中非0元素个数。
无向图的邻接矩阵中非零元个数 = 2*无向图边数
有向图邻接矩阵的特性
对顶点vi,第i行的非0元素的个数是其出度OD(vi);第i列的非0元素的个数是其入度ID(vi) 。
邻接矩阵中非0元素的个数就是图的弧的数目。

3 图的邻接矩阵的创建
图的邻接矩阵的实现比较容易,定义两个数组分别存储顶点信息(数据元素)和边或弧的信息(数据元素之间的关系) 。其存储结构情势定义以下:

#define MAXVEX 100 /* 最大顶点数,应由用户定义 */ #define INFINITY 65535 typedef char VertexType; /* 顶点类型应由用户定义 */ typedef int EdgeType; /* 边上的权值类型应由用户定义 */ typedef struct { VertexType vexs[MAXVEX]; /* 顶点表 */ EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵,可看做边表 */ int numVertexes, numEdges; /* 图中当前的顶点数和边数 */ }MGraph;
(1) 图的创建 /* 建立无向网图的邻接矩阵表示 */ void CreateMGraph(MGraph *G) { 输入顶点数numVertexes和边数numEdges ; for(i = 0;i <G-> numVertexes;i++) 读入顶点信息,建立顶点表 for(i = 0;i <G-> numVertexes;i++) for(j = 0;j <G-> numVertexes;j++) G->arc[i][j]=INFINITY;/* 邻接矩阵初始化 */ for(k = 0;k <G->numEdges;k++) 读入numEdges条边,建立邻接矩阵 }
   其他操作

(2) 图的顶点定位
肯定1个顶点在vexs数组中的位置(下标) ,其进程完全同等于在顺序存储的线性表中查找1个数据元素。
根据下标,读出顶点信息。
(3) 向图中增加顶点
类似在顺序存储的线性表的末尾增加1个数据元素。
(4) 向图中增加1条弧
根据给定的弧或边所依附的顶点,修改邻接矩阵中所对应的数组元素。

邻接链表法

基本思想:数组与链表相结合。
具体办法:
顶点用1个1维数组存储,每一个数据元素还需要存储指向第1个邻接点的指针。
每一个顶点vi的所有邻接点构成1个单链表,无向图称为顶点vi的边(链)表,有向图称为顶点vi作为弧尾的出边表(或作为弧头的入边表

邻接表的相干操作

求某结点的度,只需查找该顶点的边表中结点的个数(或直接将顶点结点的结构再增加1项,用以存储其邻接点的个数);
判断顶点vi到vj是不是存在边,检查顶点vi的边表中是不是存在结点vj的下标j便可;
求顶点的所有邻接点,只需对该顶点的边表进行遍历便可。
注:在无向图的邻接表中,边表结点的个数=2 * 边数
2 邻接表法的特点
◆ 在边或弧稀疏的条件下,用邻接表表示比用邻接矩阵表示节省存储空间;
◆ 在无向图,顶点Vi的度是第i个链表的结点数;
◆ 对有向图可以建立正邻接表或逆邻接表。正邻接表是以顶点Vi为出度(即为弧的出发点)而建立的邻接表;逆邻接表是以顶点Vi为入度(即为弧的终点)而建立的邻接表;
◆ 在有向图中,第i个链表中的结点数是顶点Vi的出 (或入)度;求入 (或出)度,须遍历全部邻接表;

3 结点及其类型定义 #define MAX_VEX 30 /* 最大顶点数 */ typedef char VertexType; /* 顶点类型应由用户定义 */ typedef int EdgeType; /* 边上的权值类型应由用户定义 */ typedef struct EdgeNode /* 边表结点 */ { int adjvex; /* 邻接点域,存储该顶点对应的下标 */ EdgeType info; /* 用于存储权值,对非网图可以不需要 */ struct EdgeNode *next; /* 链域,指向下1个邻接点 */ }EdgeNode;
typedef struct VertexNode /* 顶点表结点 */ { VertexType data; /* 顶点域,存储顶点信息 */ /* int indegree ; //顶点的度, 有向图是入度或出度 (亦可不要) */ EdgeNode *firstarc; /* 边表头指针 */ }VertexNode, AdjList[MAX_VEX]; typedef struct { AdjList adjList; //顶点数组(亦成为头结点向量) int numNodes,numEdges; /* 图中当前顶点数和边数 */ }GraphAdjList;

利用上述的存储结构描写,可方便地实现图的基本操作。

(1) 图的创建 /* 建立图的邻接表结构 */ void CreateALGraph(GraphAdjList *G) { 输入顶点数G->numNodes和边数G->numEdges for(i = 0;i < G->numNodes;i++) 读入顶点信息 G->adjList[i].data, G->adjList[i].firstedge)/* 将边表置为空表 */ for(k = 0;k < G->numEdges;k++) /* 建立边表 */ { 输入边(vi,vj)上的顶点序号; 向内存申请空间,生成边表结点; 将新生成的结点插入到以顶点vi为头结点的链表上; ( 用头插入法or尾插入法方便?) 此处需注意:如果是无向图,1条边对应两个顶点,所以应同时修正以vi为头结点和以vj为头结点的链表。 } }

其他操作:
(2) 图的顶点定位
图的顶点定位实际上是肯定1个顶点在AdjList数组中的某个元素的data域内容。
(3) 向图中增加顶点
向图中增加1个顶点的操作,在AdjList数组的末尾增加1个数据元素。
(4) 向图中增加1条弧
根据给定的弧或边所依附的顶点,修改单链表:无向图修改两个单链表;有向图修改1个单链表。

10字链表法

10字链表(Orthogonal List)是有向图的另外一种链式存储结构,是将有向图的正邻接表和逆邻接表结合起来得到的1种链表。
在这类结构中,每条弧的弧头结点和弧尾结点都寄存在链表中,并将分别组织到以弧尾结点为头(顶点)结点和以弧头结点为头(顶点)结点的链表中。

data域:存储和顶点相干的信息; ◆ firstin:指向以该顶点为弧头的第1条弧所对应的弧结点; ◆ firstout:指向以该顶点为弧尾的第1条弧所对应的弧结点; ◆ tailvex:唆使弧尾顶点在顶点表中的下标; ◆ headvex:唆使弧头顶点在顶点表中的下标; ◆ hlink:指向弧头相同的下1条弧; ◆ tlink:指向弧尾相同的下1条弧; ◆ Info域:指向该弧的相干信息,如网的权值
结点类型定义 #define INFINITY MAX_VAL /* 最大值∞ */ #define MAX_VEX 30 // 最大顶点数 typedef struct ArcNode { int tailvex , headvex ; // 尾结点和头结点在顶点表中的下标; InfoType info ; // 与弧相干的信息, 如权值 struct ArcNode *hlink , *tlink ; }ArcNode ; /* 弧结点类型定义 */ typedef struct VexNode { VexType data; // 顶点信息 ArcNode *firstin , *firstout ; }VexNode ; /* 顶点结点类型定义 */ typedef struct { int vexnum ; VexNode xlist[MAX_VEX] ; }OLGraph ; /* 图的类型定义 */

邻接多重表(Adjacency Multilist)

邻接多重表(Adjacency Multilist)是无向图的另外一种链式存储结构。 在无向图的邻接表中,1条边(v,w)的两个表结点分别被选在以v和w为头结点的链表中。如果关注的重点是顶点,则邻接表是不错的选择,但在触及到边的操作会带来不便。 邻接多重表的结构和10字链表类似,每条边用1个结点表示;邻接多重表中的顶点结点与邻接表中的完全相同

Data域:存储和顶点相干的信息;
firstedge:指向依附于该顶点的第1条边所对应的表结点;
mark:用以标识该条边是不是被访问过;
ivex和jvex:分别保存该边所依附的两个顶点在顶点表中的下标;
info域:保存该边的相干信息;
ilink:指向依附于顶点ivex的下1条边;
jlink:指向依附于顶点jvex的下1条边;

结点类型定义 #define INFINITY 65535 /* 最大值∞ */ #define MAX_VEX 30 /* 最大顶点数 */ typedef emnu {unvisited , visited} Visitting ; typedef struct EdgeNode { Visitting mark ; // 访问标记 int ivex , jvex ; // 该边依附的两个结点在图中的位置 InfoType info ; // 与边相干的信息, 如权值 struct EdgeNode *ilink , *jlink ; // 分别指向依附于这两个顶点的下1条边 }EdgeNode ; /* 弧边结点类型定义 */
typedef struct VexNode { VexType data; // 顶点信息 ArcNode *firsedge ; //指向依附于该顶点的第1条边 }VexNode ; /* 顶点结点类型定义 */ typedef struct { int vexnum ; VexNode mullist[MAX_VEX] ; }AMGraph ;

图的边表存储结构

在某些利用中,有时主要考察图中边的权值和所依附的两个顶点,即图的结构主要由边来表示,称为边表存储结构。
边表结构采取顺序存储,用2个1维数组构成,1个存储顶点信息,1个存储边的信息。边数组的每一个元素由3部份组成:
边的出发点下标
边的终点下标
边的权值

边表存储结构的情势描写以下: #define INFINITY MAX_VAL /* 最大值∞ */ #define MAX_VEX 30 /* 最大顶点数 */ #define MAX_EDGE 100 /* 最大边数 */ typedef struct ENode { int begin , end ; /* 边所依附的两个顶点 */ WeightType weight ; /* 边的权值 */ }ENode ; /* 边表元素类型定义 */ typedef struct { int vexnum , edgenum ; /* 顶点数和边数 */ VexType vexs[MAX_VEX] ; /* 顶点表 */ ENode edges[MAX_EDGE] ; /* 边表 */ }ELGraph ;
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐