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

数组表示法

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

• 形式描述如下：

#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 的入度。