邻接矩阵 - wangshengliang

常见的存储方式有2种：

所谓邻接矩阵，本质上就是使用一个 二维数组 来存储图。举个例子，假设有如下的 有向图：

那么使用一个二维数组存储的结构如下：

\left[ \begin{matrix} 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 \end{matrix} \right]

每一行代表一个顶点，每一列也代表一个顶点。例如上面的图有 5 个顶点，那么这个二维数组就是 5 x 5 的二维数组。如果是 n 个顶点，那么这个二维数组就是 n x n。

1 表示顶点之间是有连接关系的。V1 顶点连接 V2，因此第一行第二列就是 1，V1 顶点连接 V4，因此第一行第四列就是 1.

接下来是无向图，如下：

使用邻接矩阵的表示法来表示的话，如下：

\left[ \begin{matrix} 0 & 1 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 1\\ 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 \end{matrix} \right]

因为无向路是没有方向的，因此 V1 顶点连接 V2 顶点的同时，V2 顶点也连接 V1 顶点。

带边权的图

另外，我们知道图可以是带边权的，此时在二维数组中 存储的就是具体的边权值，而非简单的记入 1。

下面是具体的例子。首先是带边权的有向图：

表示出来就是：

\left[ \begin{matrix} \infty & 5 & \infty & 4 & \infty\\ \infty & \infty & \infty & \infty & 4\\ \infty & 1 & \infty & \infty & \infty\\ \infty & \infty & 2 & \infty & \infty\\ \infty & \infty & 2 & \infty & \infty \end{matrix} \right]

注意，现在没有相连的两个顶点，不能用 0 来表示，因为 0 会存在歧义，被误解为边权值。JS 里面就可以使用 Infinity

下面是带边权的无向图示例：

表示出来就是：

\left[ \begin{matrix} \infty & 5 & \infty & 4 & \infty\\ 5 & \infty & 1 & \infty & 4\\ \infty & 1 & \infty & 2 & 2\\ 4 & \infty & 2 & \infty & \infty\\ \infty & 4 & 2 & \infty & \infty \end{matrix} \right]

使用邻接矩阵来存储图的优缺点如下：

优点

（1）容易判断两个顶点是否有边，例如要判断 V1 和 V2 这两个顶点是否有边，只需要看二维数组 arr[0][1] 和 arr[1][0] 是否有值即可。

（2）容易计算顶点的度。度还可以分为出度和入度。V2 顶点的出度，指的是 V2 顶点指向其他边的数量，下图中 V2 顶点的出度就是 1. 入度指的是指向当前顶点的边的数量，V2 的入度就为 2.

上图使用邻接矩阵表示出来：

\left[ \begin{matrix} 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 \end{matrix} \right]

该顶点对应的行的 1 的数量就是该顶点出度的数量，该顶点对应的列的 1 的数量就是入度的数量。

缺点

（1）统计 边的数量 的效率较低，需要去遍历二维数组，时间复杂度为 O(n²)

（2）空间复杂度高，因为是二维数组来存储，因此空间复杂度也是 O(n²)

-EOF-