数据结构——图的存储举例

杨伟彬
杨伟彬   发布于 2018-12-28 14:33
阅读量: 337

1. 图的定义

       (Graph) 是一种复杂的非线性数据结构, 由顶点集合及顶点间的关系(也称弧或边)集合组成。可以表示为:G=(V, VR)其中V是顶点的有穷非空集合; VR 是顶点之间关系的有穷集合,也叫做弧或边集合。是顶点的有序对,是顶点的无序对。

       若<v, w>∈VR,则<v, w>表示从v到w的一条弧,且称v为弧尾,称w为弧头,此时的图称为有向图

       若<v, w>∈VR 必有<w, v>∈VR,则以无序对(v, w)代表这两个有序对,表示v和w之间的一条边,此时的图称为无向图

      

       根据图的组成,我们只要把顶点和边(或弧)的集合储存起来,那么该图的所有数据就能够存储起来了,本文介绍四种比较常见和重要的图的存储结构:邻接矩阵、邻接表、十字链表和邻接多重表。

2. 邻接矩阵存储表示

      一个有n个顶点的图,可用两个数组存储。其中一个一维数组存储数据元素(顶点)的信息,另一个二维数组(邻接矩阵)存储数据元素之间的关系(边或弧)的信息。

特点

①无向图的邻接矩阵对称,可压缩存储;有n个顶点的无向图所需存储空间为 n(n-1)/2;

②有向图的邻接矩阵不一定对称;有n个顶点的有向图所需存储空间为n²,用于稀疏图时空间浪费严重;

③无向图中顶点\(v_i\)的度TD(\(v_i\))是邻接矩阵中第i行1的个数;

④有向图中 顶点\(v_i\)出度是邻接矩阵中第i行1的个数;顶点\(v_i\)入度是邻接矩阵中第i列1的个数。

网的邻接矩阵为:

             因此,采用邻接矩阵存储表示如下:

#define	INFINITY INT_MAX	//整型的最大值∞

#define MAX_VERTEX_NUM 20	//最大顶点个数
typedef enum
{
	DG,DN,UDG,UDN				//有向图,有向网,无向图,无向网
}GraphKind;					

typedef struct 
{
	VRType adj;		//VRType是顶点关系类型对无权图,用1或0表示是否邻接
	InfoType *info;	//该弧相关信息的指针
} ARCCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
	VertexType vexs[MAX_VERTEX_NUM];//顶点向量用来标记哪个顶点
	AdjMatrix arcs;					  //邻接矩阵
	int vexnum, arcnum;				  //图的当前顶点数和弧数
	GraphKind kind;					  //图的种类标志
}MGraph;

2. 邻接表存储表示

       对于顶点数很多但是边数很少的图来说,用邻接矩阵显得略为“奢侈”,因为矩阵元素为1的很少,即其中的有用信息很少,但却占了很大的空间。所以下面我们来看看邻接表:

       邻接表是图的一种链式存储结构。在邻接表中,对图中的每个顶点建立一个单链表,第i个单链表中的结点依附于顶点\(v_i\)的边(对有向图是以顶点\(v_i\)为尾的弧)。每个单链表上附设一个表头结点。

  表结点由三个域组成,adjvex存储与\(v_i\)邻接的点在图中的位置,nextarc存储下一条边或弧的结点,data存储与边或弧相关的信息如权值。头结点由两个域组成,firstarc指向链表中第一个顶点,data存储\(v_i\)的名或其他信息。

     

邻接表的特点

①表示不唯一;

②对于稀疏图,邻接表比邻接矩阵更省空间;

③对于无向图,\(v_i\)对应第i个链表的表结点个数等于顶点得度;对于有向图,\(v_i\)对应第i个链表的表结点个数等于顶点的出度,其入度为邻接表中所有adjvex值域为i的边结点数目;

④若无向图中有n个顶点、e条边,则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图。

因此,采用邻接表存储表示如下:

#define MAX_VERTEX_NUM 20
typedef struct ArcNode//表结点类型
{
	int   adjvex;					//该弧指向顶点位置 0,1,2,3...
	struct ArcNode * nextarc;	//指向下一条弧的指针
	InfoType *info;				//该弧相关信息的指针
}ArcNode;

typedef struct VNode//头结点类型
{
	VertexType data;		//顶点信息(VertexType实际上是顶点类型)
	ArcNode *firstarc;	//指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct//邻接表类型
{
	AdjList vertices;	
	int vexnum, arcnum;	//图的顶点数和弧数
	int kind;				//图的类型标志
}ALGraph;

3. 十字链表存储表示

       该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图,可以达到高效的存取效果。

  

       顶点结点有三个域组成,data域存储和顶点相关的信息,firstin域存储第一条入弧,firstout域存储第一条出弧。弧结点有四个域,尾域tailvex和头域headvex分别指示弧尾和弧头这两个顶点在图中的位置,链域hlink指向弧头相同的下一条弧,链域tlink指向弧尾相同的下一条弧,还有info域指向该弧的相关信息。

   

采用十字链表存储表示如下:

typedef struct ArcBox	//弧结点的结构
{
	int tailvex, headvex;			//该弧的尾和头顶点的位置
	struct ArcBox *hlink,*tlink;	//分别为弧头相同和弧尾相同的弧的链域
	InfoType *info;					//该弧相关信息的指针
}ArcBox;

typedef struct VexNode	//顶点结点结构
{
	VertexType data;				//顶点信息(VertexType实际上是顶点类型)
	ArcBox *firstin, *firstout;//分别指向该顶点第一条入弧和出弧
}VexNode;

typedef struct //十字链表结构
{
	VexNode xlist[MAX_VERTEX_NUM];//表头向量
	int vexnum, arcnum;			  	//有向图的当前顶点数和弧数
}OLGraph;

4. 多重邻接表存储表示

       邻接多重表是无向图的另一种链式存储结构。虽然在邻接表是无向图的一种很有效的存储结构,在邻接表中容易求得顶点和边的各种信息,但是对边进行操作比较繁琐(如:删除一条边需找表示此边的两个结点)。

邻接多重表:每条边用一个结点表示。其结点结构如下

  

       边结点:mark域是存储标志域标记此边是否被搜索过,ivex域和jvex域是该边依附的两个顶点在表头数组中位置,ilink域指向依附于ivex的下一条边,jlink域指向依附于jvex的下一条边,info域指向该弧的相关信息。

       顶点结点:data域存与顶点有关的信息,firstedge域指向第一条依附于该顶点的边。

采用邻接多重表存储表示如下

typedef enum
{
	unvisited, visited
} VisitIf;

typedef struct EBox	//边结点的结构
{
	VisitIf mark;				//访问标记
	int ivex, jvex;			//该边依附的两个顶点的位置
	struct EBox *ilink, *jlink;//分别指向依附这两个顶点的下一条边
	InfoType *info;				//该边信息指针
}EBox;

typedef struct VexBox	//顶点结点的结构
{
	VertexType data;
	EBox *firstedge;		//指向第一条依附该顶点的边
}VexBox;

typedef struct			//邻接多重表结构
{
	VexBox adjmulist[MAX_VERTEX_NUM];
	int vexnum, adgenum;//无向图的当前顶点数和边数
}AMLGraph;

 

收藏 转发 评论