邻接矩阵

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

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

阶为${\displaystyle n}$的图${\displaystyle G}$的邻接矩阵${\displaystyle A}$是${\displaystyle n\times <!--\; \times \; -->n}$的。将${\displaystyle G}$的顶点标签为${\displaystyle v_1,v_2,...,v_n}$。若${\displaystyle (v_i,v_j)\in <!--\; \in \; -->E(G)}$，${\displaystyle A_{ij}=1}$，否则${\displaystyle A_{ij}=0}$。也可以用大于0的值表示边的权值，例如可以用边权值表示一个点到另一个点的距离。

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

可以用矩阵表示为：

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

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

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

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

非矩阵解法：

矩阵解法：

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

主要缺点包括：

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