邻接矩阵
邻接矩阵
在图论和计算机科学中，邻接矩阵（）是一种方阵，用来表示有限图。它的每个元素代表各点之间是否有边相连。
作为特例，简单图的邻接矩阵是(0,1)矩阵并且对角线元素都为0。无向图的邻接矩阵是对称矩阵。图和其邻接矩阵的特征值和特征向量之间的关系是谱图理论的研究对象。
图的-{zh-hans:关联矩阵;zh-hant:关联矩阵}-需要和邻接矩阵区分。它是图的另一种矩阵表示方式，它的元素表示各个节点-边对是否相关。还有图的度数矩阵，含有每个结点的度数信息。
距离矩阵可算是邻接矩阵的扩充。
定义.
阶为formula_1的图formula_2的邻接矩阵formula_3是formula_4的。将formula_2的顶点标签为formula_6。若formula_7，formula_8，否则formula_9。也可以用大于0的值表示边的权值，例如可以用边权值表示一个点到另一个点的距离。
无向图的邻接矩阵是对称矩阵。
例子.
无向图.
无向图的邻接矩阵计算方法是每条边为对应的单元加上1，而每个自环加上2。这样让某一节点的度数可以通过邻接矩阵的对应行或者列求和得到。
有向图.
有向图的邻接矩阵可以是不对称的。我们可以定义有向图的邻接矩阵中的某个元素Aij代表：
第一种定义广泛用于图论和社会网络分析（如：社会学、政治学、经济学、心理学）。第二种更加常见于其他应用学科（如：动态系统、物理、网络学），这些学科有时用邻接矩阵A表示图上的线性动力。
在第一种定义下，有向图的某个节点的入度可以通过对应的列（column）求和而得，出度可以通过对应的行（row）求和而得。在第二种定义下，入度可以通过对应的行（row）求和而得，出度可以通过对应的列（column）求和而得。
特性.
设图formula_2的邻接矩阵为formula_3，边的取值为1。
应用.
传球问题.
A、B、C、D四人传球6次，从A开始，最终回到A手里，有多少种传法？
非矩阵解法：
矩阵解法：
formula_27
图论算法的计算机实践.
邻接矩阵法是比较简单的图论问题建模方法，它以方形二维阵列的形式存储图的数据。它在算法应用中的主要特点包括：
主要缺点包括：
随机过程.
在随机过程理论中，表示单步状态变化的转移矩阵就是一种邻接矩阵。
本站由爱斯园团队开发维护，感谢那些提出宝贵意见和打赏的网友，没有你们的支持，网站不可能发展到今天，
继往开来，善终如始，我们将继续砥砺前行。
Copyright ©2014 iissy.com, All Rights Reserved.