7.2.1　邻接矩阵表示法

图的邻接矩阵表示法也称作数组表示法。它采用两个数组来表示图：一个是用于存储顶点信息的一维数组，另一个是用于存储图中顶点之间关联关系的二维数组，称为邻接矩阵。

对于一个具有n个顶点的图，可以使用n×n的矩阵（二维数组）来表示它们间的邻接关系。如图7－11和图7－12分别是无向图和有向图的邻接矩阵表示，矩阵A（i，j）＝1表示图中存在一条边（vi，vj），而A（i，j）＝0表示图中不存在边（vi，vj）。

假设G是一具有n个结点的无权图，G的邻接矩阵是具有如下性质的n×n矩阵A：

图7－11 无向图邻接矩阵

图7－12 有向图邻接矩阵

图7－11所示是无向图的邻接矩阵表示法，可以观察到，矩阵沿对角线对称，即A（i，j）＝A（j，i）。无向图邻接矩阵的第i行或第i列非零元素的个数其实就是第i个顶点的度。这表示无向图邻接矩阵存在一定的数据冗余。

图7－12所示是有向图邻接矩阵表示法，矩阵并不沿对角线对称，A（i，j）＝1表示顶点vi邻接到顶点vj；A（j，i）＝1则表示顶点vi邻接自顶点vj。两者并不像无向图邻接矩阵那样表示相同的意思。有向图邻接矩阵的第i行非零元素的个数其实就是第i个顶点的出度，而第i列非零元素的个数是第i个顶点的入度，即第i个顶点的度是第i行和第i列非零元素个数之和。

若图G是一个有n个结点的网，则它的邻接矩阵是具有如下性质的n×n矩阵

例如，图7－13就是一个有向网及其邻接矩阵的示例。其中对角线值为0，若两点之间有弧存在即在对应的矩阵位置写权值，若没有边存在即是∞。

图7－13 有向图网络的邻接矩阵

邻接矩阵表示法的C语言描述结构定义如下：

下面给出用邻接矩阵法创建有向网的算法。

算法7.1 采用邻接矩阵表示法创建有向图

该算法的时间复杂度为O（n2＋e×n），其中O（n2）时间耗费在对二维数组arcs的每个分量的arj域初始化赋值上。O（e×n）的时间耗费在有向网中边权的赋值上。

邻接矩阵法的特点如下。

（1）存储空间。对于无向图而言，它的邻接矩阵是对称矩阵（因为若（vi，vj）∈E（G），则（vj，vi）∈E（G）），因此我们可以采用特殊矩阵的压缩存储法，即只存储其下三角即可，这样一个具有n个顶点的无向图G，它的邻接矩阵需要n（n－1）／2个存储空间即可。但对于有向图而言，其中的弧是有方向的，即若＜vi，vj＞∈E（G），不一定有＜vj，vi＞∈E（G），因此，有向图的邻接矩阵不一定是对称矩阵，对于有向图的邻接矩阵的存储则需要n2个存储空间。

（2）便于运算。采用邻接矩阵表示法，便于判定图中任意两个顶点之间是否有边相连，即根据A［i，j］＝0或1来判断。另外，还便于求得各个顶点的度。对于无向图而言，其邻接矩阵第i行元素之和就是图中第i个顶点的度。