---
# System prepended metadata

title: 【7-1】鄰接矩陣 & 鄰接表

---

# 【7-1】鄰接矩陣 & 鄰接表

我們要怎麼把一張圖 (graph) 存下來呢？當然不是按下載鍵這麼簡單。

對於一條邊，我們有三個需要紀錄的東西：
```
起點 終點 邊權
```
其中對於無向圖，在上一章我們知道，可以將無向邊視為兩條有向邊。

對於無加權圖，我們可以簡單的將邊權視為 1。

## 鄰接矩陣 (Adjacency Matrix)

鄰接矩陣是一種用二維陣列表示圖的方式。如果圖有 $n$ 個節點，建立一個 $n \times n$ 的矩陣 `adj`，其元素定義如下：

$$
adj[i][j] =
\begin{cases}
x & \text{有一條由節點 } i \text{ 通往節點 } j \text{ 的有向邊} \\
0 & \text{}
\end{cases}
$$

對於加權圖，可以把 x 改成邊的權重，沒有邊則設為 1。

## 鄰接矩陣模板

1. 有向加權圖
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m; // 節點數, 邊數
    cin >> n >> m;
    vector<vector<int>> adj(n, vector<int>(n, 0));
    for(int i=0;i<m;i++){
        int x,y,d;
        cin >> x >> y >> d;
        adj[x][y]=d;
    }
}
```
2. 無向加權圖
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m; // 節點數, 邊數
    cin >> n >> m;
    vector<vector<int>> adj(n, vector<int>(n, 0));
    for(int i=0;i<m;i++){
        int x,y,d;
        cin >> x >> y >> d;
        adj[x][y]=d;
        adj[y][x]=d; // 把無向邊拆成兩個有向邊
    }
}
```
3. 有向無加權圖
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m; // 節點數, 邊數
    cin >> n >> m;
    vector<vector<bool>> adj(n, vector<int>(n, false));
    for(int i=0;i<m;i++){
        int x,y;
        cin >> x >> y;
        adj[x][y]=true;
    }
}
```
4. 無向無加權圖
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m; // 節點數, 邊數
    cin >> n >> m;
    vector<vector<bool>> adj(n, vector<int>(n, false));
    for(int i=0;i<m;i++){
        int x,y;
        cin >> x >> y;
        adj[x][y]=true;
        adj[y][x]=true;
    }
}
```

## 鄰接表 (Adjacency List)

鄰接表用陣列，每個節點存一個「鄰居列表」，用來表示與哪些節點有邊連接。

$$
adj[i] = \text{節點 } i \text{ 的鄰居集合}
$$

對於加權圖，每個鄰居可以存成 `(鄰居節點, 權重)` 的形式。

## 鄰接表模板

1. 有向加權圖
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m; // 節點數, 邊數
    cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n); // (鄰居節點, 權重)
    for(int i=0;i<m;i++){
        int x,y,d;
        cin >> x >> y >> d;
        adj[x].push_back({y,d});
    }
}
```
2. 無向加權圖
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m; // 節點數, 邊數
    cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n); // (鄰居節點, 權重)
    for(int i=0;i<m;i++){
        int x,y,d;
        cin >> x >> y >> d;
        adj[x].push_back({y,d});
        adj[y].push_back({x,d});
    }
}
```
3. 有向無加權圖
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m; // 節點數, 邊數
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for(int i=0;i<m;i++){
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y);
    }
}
```
4. 無向無加權圖
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m; // 節點數, 邊數
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for(int i=0;i<m;i++){
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}
```

## 鄰接矩陣 vs 鄰接表比較

原則上都會使用鄰接表，以下是詳細的複雜度比較：

| 特性      | 鄰接矩陣              | 鄰接表                   |
| ------- | ----------------- | --------------------- |
| 空間複雜度   | $O(n^2)$          | $O(n + m)$            |
| 查詢邊是否存在 | $O(1)$            | $O(\text{degree}(i))$ |
| 遍歷鄰居    | $O(n)$            | $O(\text{degree}(i))$ |
| 適用圖類型   | 稠密圖 (dense graph) | 稀疏圖 (sparse graph)    |

---

聯絡方式：codecodefunny@gmail.com
最後編修時間：2025/09/07 子柚筆