数据结构图的定义和存储结构

图（Graph）是由顶点（图中的结点称为图的顶点）的非空有限集合V（由N0个顶点组成）与边的集合E（顶点之间的关系）所构成的。

根据“存数据存联系”的存储原则，由图的定义可知，图是由顶点和边组成的，因此在存储中，除了要存储结点的信息，还要存储边的信息。

图结构中的结点间没有确定的关系，任意两点之间都可能存在联系，因此无法像树结构那样用顺序结构既存放结点数据，同时又存放结点间的关系，但如果把顶点和边的信息分开存放在顺序结构中，则应该是可以的。

1 图的数组表示法

1.1 邻接矩阵

1.2 边集数组

2 图的链表表示法

2.1 邻接表

2.2 十字链表

2.3 邻接多重表

3 存储结构的比较

1 图的数组表示法

1.1 邻接矩阵

顶点集：一维数组vertex[n] （一个具有n个顶点的图）；

1.2 边集数组

顶点集：一维数组；

边集：一维数组（数组元素为结构体）；

typedef struct{

VexType start_vex;

VexType end_vex;

InfoType weight;

} EdgeStruct;

EdgeStruct EdgeSet[Edge_MAX_NUM];

2 图的链表表示法

2.1 邻接表

图中的边是由每个顶点Vi与其邻接点构成，每个顶点Vi的所有邻接点构成一个线性表，考虑图的一般情形，对任一顶点Vi来说，邻接点的个数不确定，因此选择用单链表来存储，即对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接结点。

余下为的问题是如何把这n个单链表组织在一起，便于管理。对n个单链表并行管理可以采用“带行向量的链表表示方法”，称为邻接表。邻接表是图的一种链式存储结构，由头结点表和邻接结点链表组成：

头结点表：一维数组（数组元素为结构体，结构体的指针链指向邻接结点链表）

邻接结点链表：链接线性表（单链表）

在有向图中，有入度和出度的概念。有向图的顶点vi的入度是指以顶点vi为终点的弧的数目。顶点vi的出度是指以vi为起始点的弧的数目。入度和出度的和为有有向图顶点vi的度。有向图的邻接表只描述顶点的出度：

有向图的逆邻接表只描述顶点的入度：

实例代码：

#include stdio.h

#include stdlib.h

#define TRUE 1

#define FALSE 0

#define N 8

typedef int VexType;

int AdjMatrix[N][N]=

{{0,1,1,0,0,0,0,0},

{1,0,0,1,1,0,0,0},

{1,0,0,0,0,1,1,0},

{0,1,0,0,0,0,0,1},

{0,1,0,0,0,0,0,1},

{0,0,1,0,0,0,1,0},

{0,0,1,0,0,1,0,0},

{0,0,0,1,1,0,0,0}};

typedef struct Adjnode

{

int adjvex;

struct AdjNode *next;

} AL_AdjNode;

typedef struct

{

VexType vertex;

struct AdjNode *link;

} AL_VexNode;

void Create_AdjList()

{

int i,j;

AL_VexNode VexList[N]={0,NULL};

AL_AdjNode *Ptr,*nextPtr;

for(i=0;iN;i )

{

VexList[i].vertex=i;

VexList[i].link=NULL;

j=0;

while(jN)

{

if(AdjMatrix[i][j]!=0)

{

Ptr=(AL_AdjNode*)malloc(sizeof(AL_AdjNode));

Ptr-adjvex=j;

Ptr-next=NULL;

if(VexList[i].link==NULL)

{

VexList[i].link=Ptr;

nextPtr=Ptr;

}

else

{

nextPtr-next=Ptr;

nextPtr=Ptr;

}

}

j ;

}

}

}

int main()

{

Create_AdjList();

system("pause");

return 0;

}

2.2 十字链表

如果想同时求得有向图某一个顶点的出度和入度，则需要同时存储邻接表和逆邻接表。十字链表也可以理解为将行的单链表和列的单链表结合起来存储稀疏矩阵，每个结点表示一个非零元素。

2.3 邻接多重表

对于无向图，如何设计每条边只出现一次的链表存储形式？可以借鉴边集数组对边的描述方式，一条边为一个边结点，再将边结点之间的联系通过同顶点的线索链接起来即可。由于一条边关联两个顶点，所以一个边结点要设置两个指针域。

邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，邻接多重表中，每一条 边的信息用一个结点描述，一条边对应一个边结点。边结点除了边关联的两个顶点ivex、jvex外，再加上与这两个边结点边接接的边结点位置。

在下图中，无向图的边集数组给出了每条边的信息（可以按照起点i在外循环、终点j在内循环，从小到大的顺序排列）。根据边信息，再确定i连接边、j连接边的结点对应位置，如对应边a(v0,v1)，起点v0（边集数组中值为0）的连接边为边b(v0,v3)，终点v1（边集数组中值为1）的连接边为c(v1,v2)。

如上图所示：

I 边的确定：v0→v1→v2→……确定a→b→c……；

II 在顶点表中，

v0的连接边有a,b，则node *firstedge为a，下一条边*ilink或*jlink为b；

v1的连接边有a,c,d，则node *firstedge为a，下一条边*ilink或*jlink为c或c后的d；

上图的i连接边和j连接边都是本连接边后的第二条连接边（如上图的边表中，i连接边和j连接边都是大于边编号的边）；

//邻接多重表的顶点结构

typedef struct vnode

{

VexType vertex;

struct node *firstedge; //指向第一条依附于该顶点的边

}AML_VertexNode;

//邻接多重表的顶点表

AML_VertexNode G[VERTEX_NUM];

//邻接多重表的边结点结构

typedef struct node

{

int ivex,jvex;

struct node *ilink, *jlink; //分别指向依附于ivex和jvex的下一条边。

}AML_EdgeNode;

3 存储结构的比较

各种存储表示各有利弊，具体应用时，要根据图的稠密和稀疏程序以及运算的要求进行选择。

存储方法	实现方法	优点	缺点	关注重点
邻接矩阵	二维数组	易判断两点间的关系	占用空间	顶点
		容易求得顶点的度
邻接表	链表	节省空间	不易判断两点间的关系	顶点
		易得到顶点的出度	不易得到顶点的入度
十字链表	链表	空间要求较小	结构较复杂	边
		易求得顶点的出度和入度
邻接多重表	链表	节省空间	结构较复杂	边
		易判断两点间的关系

－End－