# 【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. 有向加權圖

#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. 無向加權圖

#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. 有向無加權圖

#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. 無向無加權圖

#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. 有向加權圖

#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. 無向加權圖

#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. 有向無加權圖

#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. 無向無加權圖

#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) |

---

聯絡方式：[e-mail]
最後編修時間：2025/09/07 子柚筆