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