图的存储结构

一、邻接矩阵存储方法

邻接矩阵是表示顶点之间相邻关系的矩阵。

设G=(V，E)是具有n（n＞0）个顶点的图，顶点的顺序依次为0～n-1，则G的邻接矩阵A是n阶方阵，其定义如下：

（1）如果G是无向图，则：

      A[i][j]=1：若(i,j)∈E(G)   0:其他

（2）如果G是有向图，则：

      A[i][j]=1：若<i,j>∈E(G)  0:其他

（3）如果G是带权无向图，则：

      A[i][j]= wij ：若i≠j且(i,j)∈E(G)    0：i=j    ∞：其他

      A[i][j]=  wij ：若i≠j且<i,j>∈E(G)   0：i=j　∞：其他

注意：带权图和不带权图表示的元素类型不同。

带权图（不论有向还是无向图）A[i][j]用double表示，不带权图（不论有向还是无向图）A[i][j]用int表示。

用一维数组G[ ]存储有4个顶点的无向图如：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }

则顶点2和顶点0之间是有边的。

如：

邻接矩阵的特点如下：

（1）图的邻接矩阵表示是唯一的。

（2）无向图的邻接矩阵一定是一个对称矩阵。

因此，按照压缩存储的思想，在具体存放邻接矩阵时只需存放上（或下）三角形阵的元素即可。

ÿ