大话数据结构十八：图的存储结构之邻接矩阵

大话数据结构十八：图的存储结构之邻接矩阵2014-12-301. 邻接矩阵（无向图）的特点：

图的邻接矩阵存储方式是用两个数组来表示图：

1.）一个一维数组存储存储图中顶点信息。

2.）一个二维数组（称为邻接矩阵）存储图中边或弧的信息。

上图中我们设置两个数组：

顶点数组：vertex[4] = {V0，V1，V2，V3}

边数组：arc[4][4] 为对称矩阵（0表示顶点间不存在边，1表示顶点间存在边）

2. 邻接矩阵（有向图）的特点：

无向图的边构成了一个对称矩阵，貌似浪费了一半的空间，那如果是有向图来存放，会不会把资源利用好呢？

顶点数组vertex[4] = {V0，V1，V2，V3}

弧数组arc[4][4]也是一个矩阵，但因为是有向图，所以这个矩阵并不对称。

如： V1到V0有弧，所以arc[1][0] = 1，而V0到V1没有弧，所以arc[0][1] = 0

3. 邻接矩阵（网）的特点：

每条边上带有权的图就叫网。通常权值表示两点之间的距离。

这里∞表示一个计算机允许的，大于所有边上权值的值。

作者：csdn博客 zdp072