邻接矩阵法

在图论中，邻接矩阵（英语：adjacency matrix）是表示一种图结构的常用表示方法。它用数字方阵记录各点之间是否有边相连，数字的大小可以表示边的权值大小。距离矩阵可算是邻接矩阵的扩充。阶为 n {displaystyle n} 的图 G {displaystyle G} 的邻接矩阵 A {displaystyle A} 是 n × n {displaystyle ntimes n} 的。将 G {displaystyle G} 的顶点标签为 v 1 , v 2 , . . . , v n {displaystyle v_{1},v_{2},...,v_{n}} 。若 ( v i , v j ) ∈ E ( G ) {displaystyle (v_{i},v_{j})in E(G)} ， A i j = 1 {displaystyle A_{ij}=1} ，否则 A i j = 0 {displaystyle A_{ij}=0} 。也可以用大于0的值表示边的权值，例如可以用边权值表示一个点到另一个点的距离。无向图的邻接矩阵是对称矩阵。可以用矩阵表示为：这个矩阵中每一行代表一个点，行a即为点a，每一列代表某一行的点所指向的点，矩阵的每一个（小格）表示一条边。图中的所有边（指向性的箭头）带有权值，通常约定权值为0的边为不存在的边。如此图中的a指向b，箭头旁边的数字（边的权值）为2，在矩阵中表示为行a列b为2。又如矩阵中行c列b为6，图中表现为一条从c指向b权值为6的边。设图 G {displaystyle G} 的邻接矩阵为 A {displaystyle A} ，边的取值为1。A、B、C、D四人传球6次，从A开始，最终回到A手里，有多少种传法？非矩阵解法：矩阵解法：A = ( 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 ) , A 6 = ( 183 182 182 182 182 183 182 182 182 182 183 182 182 182 182 183 ) {displaystyle A={begin{pmatrix}0&1&1&1\1&0&1&1\1&1&0&1\1&1&1&0\end{pmatrix}},A^{6}={begin{pmatrix}183&182&182&182\182&183&182&182\182&182&183&182\182&182&182&183\end{pmatrix}}}邻接矩阵法是比较简单的图论问题建模方法，它以方形二维阵列的形式存储图的数据。它在算法应用中的主要特点包括：主要缺点包括：在随机过程理论中，表示单步状态变化的转移矩阵就是一种邻接矩阵。