邻接矩阵

在图论和計算機科學中，邻接矩阵（英語：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日） （中文（中国大陆））.