邻接矩阵

   逻辑结构分为两部分：V和E集合，其中，V是顶点，E是边。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。

定义

       邻接矩阵是表示顶点之间相邻关系的矩阵。设G=（v，E）是一个图，其中V=｛v1，v2，....,vn｝。G的邻接矩阵是一个具有下列性质的n阶方阵：

（1）对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为零，有向图则不一定如此。

（2）在无向图中，任一顶点的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。

（3）用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。

特点

无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+...+(n-1)=n(n-1)/2个单元。

无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。

有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。

用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。

表示法

在图的邻接矩阵表示法中：

① 用邻接矩阵表示顶点间的相邻关系

② 用一个顺序表来存储顶点信息

图的矩阵

设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：

【例】

下图中无向图G 5 和有向图G 6 的邻接矩阵分别为A1 和A 2 。

网络矩阵

若G是网络，则邻接矩阵可定义为：

其中：

w ij 表示边上的权值;

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

【例】下面带权图的两种邻接矩阵分别为A 3 和A 4 。