邻接矩阵

在图论中，邻接矩阵（英語：adjacency matrix）是表示一种图结构的常用表示方法。它用数字方阵记录各点之间是否有边相连，数字的大小可以表示边的权值大小。

距離矩陣可算是鄰接矩陣的擴充。

定义

階為$n$的圖$G$的鄰接矩陣$A$是$n\times n$的。將$G$的頂點標籤為$v_{1},v_{2},...,v_{n}$。若$(v_{i},v_{j})\in E(G)$，$A_{ij}=1$，否則$A_{ij}=0$。也可以用大于0的值表示边的权值，例如可以用边权值表示一个点到另一个点的距离。

无向图的鄰接矩陣是對稱矩陣。

例子

• 例1

可以用矩阵表示为：

${\begin{bmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{bmatrix}}$

• 例2

典型的邻接矩阵

这个矩阵中每一行代表一个点，行a即为点a，每一列代表某一行的点所指向的点，矩阵的每一个（小格）表示一条边。图中的所有边（指向性的箭头）带有权值，通常约定权值为0的边为不存在的边。

如此图中的a指向b，箭头旁边的数字（边的权值）为2，在矩阵中表示为行a列b为2。又如矩阵中行c列b为6，图中表现为一条从c指向b权值为6的边。

特性

設圖$G$的鄰接矩陣為$A$，边的取值为1。

• 如果顶点有自我连接产生的自环（loop），则在矩阵的主对角线上会有非零的值；如果没有自环，则主对角线上全部是0。
• $A^{n}$的元素$A_{ij}^{n}$可以表示由頂點$i$到頂點$j$長度為$n$的徑的數目。
• $G$沒有有向圈若且唯若$I-A$可逆。$(I-A)^{-1}$的元素$ij$表示由頂點$i$到頂點$j$的所有徑的數目。因為：$(I-A)^{-1}=I+A+A^{2}+A^{3}+...$

应用

传球问题

A、B、C、D四人传球6次，从A开始，最终回到A手里，有多少种传法？

非矩阵解法：

1. m个人传n次球，$\sum _{i=1}^{[{\frac {n}{2}}]}(m-1)^{i}(m-2)^{n-2i}C_{n-1-i}^{i-1}$
2. $(m-1)P_{n+1}=1-P_{n},P_{n}={\frac {1}{m}}(1-({\frac {-1}{m-1}})^{n-1})$，将P_n乘上总传法数$(m-1)^{n-1}$

矩阵解法：

$A={\begin{bmatrix}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\\\end{bmatrix}},A^{6}={\begin{bmatrix}183&182&182&182\\182&183&182&182\\182&182&183&182\\182&182&182&183\\\end{bmatrix}}$

图论算法的计算机实践

参见：邻接表和十字链表

邻接矩阵法是比较简单的图论问题建模方法，它以方形二维阵列的形式存储图的数据。它在算法应用中的主要特点包括：

• 各元素的取值与边的输入顺序无关。
• 利用输入数据建图之前，因为不一定每对点之间都有边相连，所以先要执行将所有边的权值设为无效值的初始化步骤。以此法建模有$n$个点和$m$条边的图，其初始化需要$O(n^{2})$的时间复杂度，建图的时间则为$O(m)$。
• 以此法建模有$n$个点和$m$条边的图，其内存空间开销的规模是$O(n^{2})$。

主要缺点包括：

• 遍历元素时，存在的边和不存在的边都不得不检查一遍，导致遍历效率低。
• 不能存储重复的边。
• 当顶点数量多时，内存空间开销会很大。
• 存储稀疏图时会得到稀疏矩阵，空间利用率不高。
• 存储无向图时，由于此时矩阵是对称的，而对称位置上的成对元素保存的信息是重复的，导致空间利用率不高。

随机过程

在随机过程理论中，表示单步状态变化的转移矩阵就是一种邻接矩阵。