在图论和計算機科學中，邻接矩阵（）是一種方块矩阵，用來表示有限图。它的每個元素代表各点之间是否有边相连。

作爲特例，簡單圖的鄰接矩陣是(0,1)矩陣並且對角線元素都爲0。無向圖的鄰接矩陣是對稱矩陣。圖和其鄰接矩陣的特徵值和特徵向量之間的關系是譜圖理論的研究對象。

圖的關聯矩陣}-需要和鄰接矩陣區分。它是圖的另一種矩陣表示方式，它的元素表示各個节点-邊對是否相關。還有圖的度數矩陣，含有每個結點的度數信息。

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

定义
階為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的值表示边的权值，例如可以用边权值表示一个点到另一个点的距离。第二种更加常见于其他应用学科（如：动态系统、物理、网络学），这些学科有时用邻接矩阵表示图上的线性动力。

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

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

• 如果顶点有自我连接产生的自环（loop），则在矩阵的主对角线上会有非零的值；如果没有自环，则主对角线上全部是0。
• A^n的元素A^n_{ij}可以表示由頂點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手里，有多少种传法？

非矩阵解法：
#m个人传n次球，\sum_{i=1}^{[\frac{n}{2}]}(m-1)^i (m-2)^{n-2i} C_{n-1-i}^{i-1}

(m-1)P_{n+1}=1-P_{n},P_n=\frac{1}{m}(1-(\frac{-1}{m-1})^{n-1})，将Pn乘上总传法数(m-1)^{n}

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

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

参考资料