邻接矩阵

在图论和电脑科学中，邻接矩阵（英语：adjacency matrix）是一种方阵，用来表示有限图。它的每个元素代表各点之间是否有边相连。

作为特例，简单图的邻接矩阵是(0,1)矩阵并且对角线元素都为0。无向图的邻接矩阵是对称矩阵。图和其邻接矩阵的特征值和特征向量之间的关系是谱图理论的研究对象。

图的关联矩阵需要和邻接矩阵区分。它是图的另一种矩阵表示方式，它的元素表示各个节点-边对是否相关。还有图的度数矩阵，含有每个结点的度数资讯。

距离矩阵可算是邻接矩阵的扩展。

定义

阶为${\displaystyle n}$的图${\displaystyle G}$的邻接矩阵${\displaystyle A}$是${\displaystyle n\times n}$的。将${\displaystyle G}$的顶点标签为${\displaystyle v_{1},v_{2},...,v_{n}}$。若${\displaystyle (v_{i},v_{j})\in E(G)}$，${\displaystyle A_{ij}=1}$，否则${\displaystyle A_{ij}=0}$。也可以用大于0的值表示边的权值，例如可以用边权值表示一个点到另一个点的距离。^[1]

无向图的邻接矩阵是对称矩阵。

例子

无向图

无向图的邻接矩阵计算方法是每条边为对应的单元加上1，而每个自环加上2。这样让某一节点的度数可以通过邻接矩阵的对应行或者列求和得到。

无向图	邻接矩阵
	${\displaystyle {\begin{pmatrix}2&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{pmatrix}}}$ 从左到右、从上到下分别代表1–6节点。

有向图

有向图的邻接矩阵可以是不对称的。我们可以定义有向图的邻接矩阵中的某个元素A_ij代表：

1. 从i指向j的边的数目
2. 从j指向i的边的数目

第一种定义广泛用于图论和社会网络分析（如：社会学、政治学、经济学、心理学）。^[2]第二种更加常见于其他应用学科（如：动态系统、物理、网络学），这些学科有时用邻接矩阵A表示图上的线性动力。^[3]

在第一种定义下，有向图的某个节点的入度可以通过对应的列（column）求和而得，出度可以通过对应的行（row）求和而得。在第二种定义下，入度可以通过对应的行（row）求和而得，出度可以通过对应的列（column）求和而得。

有向图	邻接矩阵
	${\displaystyle {\begin{pmatrix}0&1&0&1\\0&0&0&1\\1&1&0&0\\0&0&1&0\\\end{pmatrix}}}$ 从左到右、从上到下分别代表1–4节点。 采用有向图邻接矩阵的第一种定义

特性

设图${\displaystyle G}$的邻接矩阵为${\displaystyle A}$，边的取值为1。

• 如果顶点有自我连接产生的自环（loop），则在矩阵的主对角线上会有非零的值；如果没有自环，则主对角线上全部是0。
• ${\displaystyle A^{n}}$的元素${\displaystyle A_{ij}^{n}}$可以表示由顶点${\displaystyle i}$到顶点${\displaystyle j}$长度为${\displaystyle n}$的径的数目。^[4]
• ${\displaystyle G}$没有有向圈当且仅当${\displaystyle I-A}$可逆。${\displaystyle (I-A)^{-1}}$的元素${\displaystyle ij}$表示由顶点${\displaystyle i}$到顶点${\displaystyle j}$的所有径的数目。因为：${\displaystyle (I-A)^{-1}=I+A+A^{2}+A^{3}+...}$

应用

传球问题

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

非矩阵解法：

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

矩阵解法：

${\displaystyle 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}}}$

图论算法的电脑实践

参见：邻接表和十字链表

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

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

主要缺点包括：

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

随机过程

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

参考资料

1. 梁冰; 冯林. 6.1.4. 吴文虎 (主审); 房鸣 (主审); 孙琳 (责任编辑) (编). 程序设计算法基础. 大学生创意·创新·创业教育与实践系列教材 1. 北京: 高等教育出版社. 2018: 130–131. ISBN 978-7-04-049192-0 （中文（中国大陆））.
2. Borgatti, Steve; Everett, Martin; Johnson, Jeffrey, Analyzing Social Networks 2nd, SAGE, p. 20, 2018
3. Newman, Mark, Networks 2nd, Oxford University Press, p. 110, 2018
4. 刘亚国. 图论中邻接矩阵的应用. 张家口职业技术学院学报. 2007, (4) [2014-01-12]. （原始内容存档于2014-01-12） （中文（中国大陆））.
5. 吴炜超. 马涛; 何万程; 郭子伟 , 编. 传球问题的终极解法. 《人教网刊》第4期. 2011年6月23日 [2019年12月15日]. （原始内容存档于2016年3月5日） （中文（中国大陆））.