查看“︁邻接矩阵”︁的源代码

{{noteTA
|G1=Math
|G2=IT
}}
在[[图论]]和[[計算機科學]]中，'''邻接矩阵'''（{{lang-en|'''adjacency matrix'''}}）是一種方阵，用來表示有限[[图]]。它的每個元素代表各点之间是否有边相连。

作爲特例，簡單圖的鄰接矩陣是(0,1)矩陣並且對角線元素都爲0。[[無向圖]]的鄰接矩陣是[[對稱矩陣]]。圖和其鄰接矩陣的特徵值和特徵向量之間的關系是[[譜圖理論]]的研究對象。

圖的[[關聯矩陣|-{zh-hans:关联矩阵;zh-hant:關聯矩陣}-]]需要和鄰接矩陣區分。它是圖的另一種矩陣表示方式，它的元素表示各個节点-邊對是否相關。還有圖的[[度數矩陣]]，含有每個結點的度數信息。

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

== 定义 ==
階為<math>n</math>的圖<math>G</math>的鄰接矩陣<math>A</math>是<math>n \times n</math>的。將<math>G</math>的頂點標籤為<math>v_1,v_2,...,v_n</math>。若<math>(v_i,v_j) \in E(G)</math>，<math>A_{ij}=1</math>，否則<math>A_{ij}=0</math>。也可以用大于0的值表示边的权值，例如可以用边权值表示一个点到另一个点的距离。<ref name="梁冰_2018" />

[[无向图]]的鄰接矩陣是[[對稱矩陣]]。

==例子==
===無向圖===
無向圖的鄰接矩陣計算方法是每條邊爲對應的單元加上1，而每個自環加上2。這樣讓某一節點的度數可以通過鄰接矩陣的對應行或者列求和得到。
{|class="wikitable" style="text-align: center;"
!無向圖
!鄰接矩陣
|-
|[[Image:6n-graph2.svg|200px]]
|<math>\begin{pmatrix}
2 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0
\end{pmatrix}</math>
<br>从左到右、从上到下分别代表1–6节点。
|}

===有向图===
有向图的邻接矩阵可以是不对称的。我们可以定义有向图的邻接矩阵中的某个元素{{mvar|A<sub>ij</sub>}}代表：
# 从{{mvar|i}}指向{{mvar|j}}的边的数目
# 从{{mvar|j}}指向{{mvar|i}}的边的数目

第一种定义广泛用于图论和社会网络分析（如：社会学、政治学、经济学、心理学）。<ref>
{{citation
 | title=Analyzing Social Networks
 | edition=2nd
 | first1=Steve   | last1=Borgatti
 | first2=Martin  | last2=Everett
 | first3=Jeffrey | last3=Johnson
 | publisher=SAGE
 | year=2018
 | at=p.&nbsp;20
}}</ref>第二种更加常见于其他应用学科（如：动态系统、物理、网络学），这些学科有时用邻接矩阵{{mvar|A}}表示图上的线性动力。<ref>
{{citation
 | title=Networks
 | edition=2nd
 | first=Mark | last=Newman
 | publisher=Oxford University Press
 | year=2018
 | at=p.&nbsp;110
}}</ref>

<!-- 下述文本在台湾可能需要转换行列的位置 -->

在第一种定义下，有向图的某个节点的入度可以通过对应的列（column）求和而得，出度可以通过对应的行（row）求和而得。在第二种定义下，入度可以通过对应的行（row）求和而得，出度可以通过对应的列（column）求和而得。

{|class="wikitable" style="text-align: center;"
!有向圖
!鄰接矩陣
|-
|[[Image:4-tournament.svg|200px]]
|<math>\begin{pmatrix}
0 & 1 & 0 & 1\\
0 & 0 & 0 & 1\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
\end{pmatrix}</math>
<br>从左到右、从上到下分别代表1–4节点。
<br>采用有向图邻接矩阵的第一种定义
|}
== 特性 ==
設圖<math>G</math>的鄰接矩陣為<math>A</math>，边的取值为1。
* 如果顶点有自我连接产生的自环（loop），则在矩阵的主对角线上会有非零的值；如果没有自环，则主对角线上全部是0。
* <math>A^n</math>的元素<math>A^n_{ij}</math>可以表示由頂點<math>i</math>到頂點<math>j</math>長度為<math>n</math>的徑的數目。<ref>{{cite journal |url=http://www.cnki.com.cn/Article/CJFDTotal-ZJKZ200704033.htm |title=图论中邻接矩阵的应用 |author=刘亚国 |journal=张家口职业技术学院学报 |issue=4 |doi= |language=zh-cn |year=2007 |access-date=2014-01-12 |archive-date=2014-01-12 |archive-url=https://web.archive.org/web/20140112074148/http://www.cnki.com.cn/Article/CJFDTotal-ZJKZ200704033.htm |dead-url=no }}</ref>
* <math>G</math>沒有有向圈若且唯若<math>I-A</math>可逆。<math>(I-A)^{-1}</math>的元素<math>ij</math>表示由頂點<math>i</math>到頂點<math>j</math>的所有徑的數目。因為：<math>(I-A)^{-1} = I + A + A^2 + A^3 + ... </math>

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

非矩阵解法：
#m个人传n次球，<math>\sum_{i=1}^{[\frac{n}{2}]}(m-1)^i (m-2)^{n-2i} C_{n-1-i}^{i-1}</math><ref name="ball">{{cite web |url=http://www.pep.com.cn/rjwk/gzsxsxkj/2011/sxkj4/sxkj4ts/201106/t20110623_1050797.htm |author=吴炜超 |editor1=马涛 |editor2=何万程 |editor3=郭子伟 |title=传球问题的终极解法 |work=《人教网刊》第4期 |language=zh-cn |date=2011年6月23日 |access-date=2019年12月15日 |archive-date=2016年3月5日 |archive-url=https://web.archive.org/web/20160305032930/http://www.pep.com.cn/rjwk/gzsxsxkj/2011/sxkj4/sxkj4ts/201106/t20110623_1050797.htm |dead-url=no }}</ref>
# <math>(m-1)P_{n+1}=1-P_{n},P_n=\frac{1}{m}(1-(\frac{-1}{m-1})^{n-1})</math>，将P<sub>n</sub>乘上总传法数<math>(m-1)^{n}</math><ref name="ball"/>

矩阵解法：

<math>A=\begin{bmatrix}
0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 \\
\end{bmatrix},
A^6=\begin{bmatrix}
183 & 182 & 182 & 182 \\
182 & 183 & 182 & 182 \\
182 & 182 & 183 & 182 \\
182 & 182 & 182 & 183 \\
\end{bmatrix}</math>

=== 图论算法的计算机实践 ===
{{see also|邻接表|十字链表}}
邻接矩阵法是比较简单的图论问题建模方法，它以方形二维阵列的形式存储图的数据。它在算法应用中的主要特点包括：
* 各元素的取值与边的输入顺序无关。<ref name="梁冰_2018" />
* 利用输入数据建图之前，因为不一定每对点之间都有边相连，所以先要执行将所有边的权值设为无效值的初始化步骤。以此法建模有<math>n</math>个点和<math>m</math>条边的图，其初始化需要<math>O(n^2)</math>的[[时间复杂度]]，建图的时间则为<math>O(m)</math>。<ref name="梁冰_2018" />
* 以此法建模有<math>n</math>个点和<math>m</math>条边的图，其[[空间复杂度|内存空间开销]]的规模是<math>O(n^2)</math>。<ref name="梁冰_2018" />

主要缺点包括：
* 遍历元素时，存在的边和不存在的边都不得不检查一遍，导致遍历效率低。<ref name="梁冰_2018">{{cite book |title=程序设计算法基础 |author1=梁冰 |author2=冯林 |editor1=吴文虎 (主审) |editor2=房鸣 (主审) |editor3=孙琳 (责任编辑) |publisher=[[高等教育出版社]] |location=北京 |series=大学生创意·创新·创业教育与实践系列教材 |edition=1 |isbn=978-7-04-049192-0 |chapter=6.1.4 |pages=130-131 |ref={{harvid|梁冰|2018}} |language=zh-cn |year=2018}}</ref>
* 不能存储重复的边。<ref name="梁冰_2018"/>
* 当顶点数量多时，内存空间开销会很大。<ref name="梁冰_2018" />
* 存储稀疏图时会得到[[稀疏矩阵]]，空间利用率不高。<ref name="梁冰_2018" />
* 存储无向图时，由于此时矩阵是对称的，而对称位置上的成对元素保存的信息是重复的，导致空间利用率不高。

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

== 参考资料 ==
<references/>

{{DEFAULTSORT:adjacency matrix}}
[[Category:图论]]
[[Category:矩阵]]
[[Category:数据结构]]