邻接矩阵

(重定向自鄰接矩陣

图论中,邻接矩阵(英語:adjacency matrix)是表示一种结构的常用表示方法。它用数字方阵记录各点之间是否有边相连,数字的大小可以表示边的权值大小。

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

定义编辑

階為 的圖 的鄰接矩陣  的。將 的頂點標籤為 。若  ,否則 。也可以用大于0的值表示边的权值,例如可以用边权值表示一个点到另一个点的距离。[1]

无向图的鄰接矩陣是對稱矩陣

例子编辑

  • 例1
 

可以用矩阵表示为:

 
  • 例2
 
典型的邻接矩阵

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

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

特性编辑

設圖 的鄰接矩陣為 ,边的取值为1。

  • 如果顶点有自我连接产生的自环(loop),则在矩阵的主对角线上会有非零的值;如果没有自环,则主对角线上全部是0。
  •  的元素 可以表示由頂點 到頂點 長度為 的徑的數目。[2]
  •  沒有有向圈若且唯若 可逆。 的元素 表示由頂點 到頂點 的所有徑的數目。因為: 

应用编辑

传球问题编辑

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

非矩阵解法:

  1. m个人传n次球, [3]
  2.  ,将Pn乘上总传法数 [3]

矩阵解法:

 

图论算法的计算机实践编辑

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

  • 各元素的取值与边的输入顺序无关。[1]
  • 利用输入数据建图之前,因为不一定每对点之间都有边相连,所以先要执行将所有边的权值设为无效值的初始化步骤。以此法建模有 个点和 条边的图,其初始化需要 时间复杂度,建图的时间则为 [1]
  • 以此法建模有 个点和 条边的图,其内存空间开销的规模是 [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. ^ 刘亚国. 图论中邻接矩阵的应用. 张家口职业技术学院学报. 2007, (4) (中文(中国大陆)‎). 
  3. ^ 3.0 3.1 吴炜超. 马涛; 何万程; 郭子伟, 编. 传球问题的终极解法. 《人教网刊》第4期. 2011年6月23日 [2019年12月15日] (中文(中国大陆)‎).