图的存储结构及方法（一）

数组表示法

一个图可以用两个数组分别存储其数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

• 
  
  形式描述如下：

#define INFINITY INT MAX (最大值∞)

#define MAX VERTEX NUM 20 (最大顶点个数)

 typedef enum{DG,DN,UDG,UDN} GraphKind;

typedef struct ArcCell { ({有向图,网,无向图,网 }) 

VRType adj;(VERTYPE是顶点关系类型。对无权图，用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;

• 对于含有N个顶点的图可以用N*N的二维数组A表示

无向图如图：

无向图用邻接矩阵表示：

有向图如图：

有向图邻接矩阵表示：

• 由G1知，无向图的邻接矩阵 是一个对称矩阵，它反映了无向图中的边所代表的是对称关系。而矩阵中第i行或第i列中非零元素的个数为图中顶点v的度，可以用下面公式计算:

 n-1

 TD(vi) =∑A[i] [j](n = MAX_VERTEX_NUM)

 j=0

 同时，我们知道对称矩阵在存储时，可以用压缩的方式进行存储。即上三角或下三角。

• 由G2知，有向图的邻接矩阵为不对称矩阵，它反映了有向图中的边代表的是不对称关系。另外，图中第i行中非零元素的个数代表图中顶点vi的出度，而第i列中非零元素的个数代表图中顶点vi的入度。