在數據結構中，圖是一種由頂點（Vertex）和邊（Edge）組成的數據結構。表示圖的方法有很多，比如鄰接表、鄰接矩陣等。其中，鄰接矩陣是一種直觀且基礎的表示方式，尤其適合初學者理解。
一、什麼是鄰接矩陣？¶
鄰接矩陣本質上是一個二維數組，用於表示圖中頂點之間的連接關係。它的核心思想是：用矩陣的行和列分別對應圖的頂點，矩陣中的元素值表示兩個頂點之間是否存在邊，以及邊的權重（如果有權重）。
1. 基本定義¶
假設圖有 n 個頂點，我們將頂點編號爲 0, 1, 2, ..., n-1。鄰接矩陣是一個 n×n 的二維數組 adj，其中：
- 若 adj[i][j] = 1（或具體權重值），表示頂點 i 和頂點 j 之間存在一條邊；
- 若 adj[i][j] = 0（或無窮大 ∞），表示頂點 i 和頂點 j 之間不存在邊（對於有權圖，∞ 表示無直接邊）。
2. 示例：無向圖的鄰接矩陣¶
假設有一個無向圖，頂點爲 A, B, C, D（編號 0, 1, 2, 3），邊爲 A-B, B-C, C-D, D-A。其鄰接矩陣如下：
| A(0) | B(1) | C(2) | D(3) | |
|---|---|---|---|---|
| A(0) | 0 | 1 | 0 | 1 |
| B(1) | 1 | 0 | 1 | 0 |
| C(2) | 0 | 1 | 0 | 1 |
| D(3) | 1 | 0 | 1 | 0 |
- 例如：
adj[0][1] = 1表示頂點A和B之間有邊；adj[0][2] = 0表示A和C之間沒有邊。
二、鄰接矩陣的優點¶
-
快速判斷邊是否存在
要判斷頂點i和j之間是否有邊，只需直接訪問adj[i][j]，時間複雜度爲 O(1)。例如，在鄰接表中可能需要遍歷鏈表查找，而鄰接矩陣無需遍歷，直接通過索引定位。 -
計算頂點度高效
- 無向圖：頂點i的度（與其他頂點相連的邊數）等於鄰接矩陣第i行的元素之和（因爲無向圖中邊(i,j)同時出現在i行和j列）。
- 有向圖：頂點i的出度（從i出發的邊數）是第i行的和，入度（指向i的邊數）是第i列的和。 -
適合稠密圖
若圖中邊數較多（接近n²，即頂點數的平方），鄰接矩陣的空間利用率高。例如，一個完全圖（任意兩個頂點都有邊）的鄰接矩陣會被完全填滿，此時鄰接表反而可能因額外存儲信息而浪費空間。 -
實現簡單
對於初學者，鄰接矩陣的數組結構直觀易懂，無需複雜的數據結構（如鏈表或指針），容易理解和編碼。
三、鄰接矩陣的缺點¶
-
空間效率低
鄰接矩陣需要n×n的空間，對於 稀疏圖（邊數遠小於n²的圖），會造成大量空間浪費。例如，一個有 1000 個頂點、僅 100 條邊的稀疏圖，鄰接矩陣需要1000×1000 = 1000000個元素，而鄰接表僅需存儲 100 條邊的信息，空間優勢明顯。 -
遍歷鄰接頂點效率低
要遍歷頂點i的所有鄰接頂點，需遍歷鄰接矩陣的第i行（或列），時間複雜度爲 O(n)。例如，頂點A有 4 個鄰接頂點，在鄰接矩陣中需要遍歷 4 個頂點才能找到所有鄰居，而在鄰接表中只需直接訪問鏈表即可，時間複雜度爲 O(度)（度通常遠小於n）。 -
不適合動態調整邊數
當圖的邊數頻繁變化（如插入或刪除邊）時，鄰接矩陣需要修改數組元素，雖然修改單個元素是 O(1)，但對於大規模圖的動態操作，整體效率仍不如鄰接表靈活。
四、總結¶
鄰接矩陣的核心特點是以空間換時間：
- 適合場景：稠密圖（邊數多）、需要頻繁查詢邊是否存在、或計算頂點度的場景。
- 不適合場景：稀疏圖（邊數少）、需要頻繁遍歷鄰接頂點的場景。
對於初學者而言，鄰接矩陣是理解圖的基礎工具，通過它可以快速掌握圖的基本連接關係。但在實際應用中，需根據圖的類型（稠密/稀疏）選擇合適的表示方法。