邻接矩阵

阶为${\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。这样让某一节点的度数可以通过邻接矩阵的对应行或者列求和得到。

有向图

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

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

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

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

设图${\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-1}}$ ^[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. ^ ^{1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7} 梁冰; 冯林. 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. ^ ^{5.0 5.1} 吴炜超. 马涛; 何万程; 郭子伟 , 编. 传球问题的终极解法. 《人教网刊》第4期. 2011年6月23日 [2019年12月15日]. （原始内容存档于2016年3月5日） （中文（中国大陆））.