---
# System prepended metadata

title: '基礎圖論 (四) : 圖的表示與儲存'
tags: [內湖高中程式競賽]

---

# 基礎圖論 (四): 圖的表示與儲存
之前都是在講偏數學的觀點。這篇要把目光移回電腦上，在電腦中要儲存一張圖，需要使用相對應的資料結構，才能用點腦處理圖論問題

備註 : 這篇在沒有特別註明的情況下，圖都是 simple graph
備註 : 因為這是競程筆記，所以實作一定是 C/C++

## 鄰接矩陣 Adjacency Matrix

### 無向簡單圖 Undirected Simple Graph
從[此系列的第一篇](https://hackmd.io/@ShanC/basic-graph-theory-1)就一直強調，邊是由 relation 定義。離散數學的課本也說，relation 可以用矩陣來表示。根據此性質，一張 simple graph 用矩陣來表示是很正常的一件事。然而，要將圖以矩陣表示，每個節點就必須有編號，才能使得每個行列具有意義

我們可以定義矩陣 $A_{i, j}=\begin{cases}
1 \text{, if } (i, j)\in E\\
0 \text{, otherwise}
\end{cases}$。對於以下右圖而言，他可以用右邊的矩陣表示

<center>
<img src="https://hackmd.io/_uploads/ByUJrU8Deg.png" style="margin: 0 auto; display: block; width: 400px">
</center>

$~$
這個矩陣是對稱的。此外，若允許自環 (loop)，鄰接矩陣仍然可以表達，但是多重邊卻難以用矩陣表達，有時數字代表邊數，但**很多時候要視情況而定**。所以大多時候討論的都會是簡單圖

### 有向簡單圖 Directed Simple Graph
想當然，有向圖是由 function 表示，因此也可以用鄰接矩陣表示，但矩陣不一定會對稱

<center>
<img src="https://hackmd.io/_uploads/SySd9IUveg.png" style="margin: 0 auto; display: block; width: 400px">
</center>

### 程式實作
沒有很難，就只是二維陣列而已
```cpp
int n = 50; // 節點數
int graph[n][n];
```

空間複雜度沒什麼好說的，就是 $O(n^2)$，因此若要以鄰接矩陣確認整張圖的樣貌，時間也是 $O(n^2)$

### 鄰接矩陣的缺點
在鄰接矩陣中，如果不是完全圖，那就一定會有為 $0$ 的元素。但大多數的狀況是，我們其實不需要知道「哪些點對有連邊」，因此儲存 $0$ 的那些空間顯然很浪費。若今天存的是一張邊數與點數差不多的圖，那麼這個效果會更明顯。可以想像，若有一個邊數是 $O(n)$ 的圖，但我們卻每次都用 $O(n^2)$ 的時間去遍歷整個資料結構，那麼一定會花非常多時間

### 鄰接矩陣的優點
矩陣畢竟是一個數學物件，具有數學上的一些運算性質，像是行運算、列運算、冪次、生成函數或是特徵值等都是值得探討的事情，因此也很重要。只是電腦實作上我們更關心連通的狀況，相較之下，鄰接串列比較符合我們寫程式的需求

## 圖同構 Isomorphism
由於矩陣與圖本質上是等價的，大多圖的性質都可以從鄰接矩陣找到。其實這算是代數圖論的範疇，不是競程會去討論的內容，以下就舉幾個例子讓你有點感覺
### 定義
給定兩張圖 $A$ 與 $B$，若我們可以找出一個 bijection $f: V(A)\rightarrow V(B)$ 使得 $(u, v)\in E(A)$ 若且唯若 $(f(u), f(v))\in E(B)$，則稱為同構

||事實上，群論中的同構也差不多是這樣定義||

### 舉例說明
如下圖，$G$ 與 $H$ 就是同構

<center>
<img src="https://hackmd.io/_uploads/ryWVpIUwgx.png" style="margin: 0 auto; display: block; width: 400px">
</center>

因為我們只要將 $G$ 的 $1$ 對應到 $H$ 的 $4$、$G$ 的 $2$ 對應到 $H$ 的 $2$、$G$ 的 $3$ 對應到 $H$ 的 $3$、$G$ 的 $4$ 對應到 $H$ 的 $1$

他們的鄰接矩陣分別為 $A_G=\left[
\begin{array}{cccc}
0 & 0 & 1 & 0\\
0 & 0 & 1 & 1\\
1 & 1 & 0 & 0\\
0 & 1 & 0 & 0\\
\end{array}
\right]$ 與 $A_H=\left[
\begin{array}{cccc}
0 & 1 & 0 & 0\\
1 & 0 & 1 & 0\\
0 & 1 & 0 & 1\\
0 & 0 & 1 & 0\\
\end{array}
\right]$

如上，若要判別是否同構，可以將 $A_G$ 的行與列的 $1$ 跟 $4$ 做交換，就可以得到相同的矩陣

### 判斷同構
若要設計演算法來判別，可以窮舉所有的節點編號的排列組合，只要其中一種會使得矩陣長的一樣，則就是同構

## 邊的數量 Number of Edges
完全圖擁有一張圖最多的邊數。有了資料結構，要推出一張 $n$ 個節點的圖最多的邊數就不是個問題。以下假設無向圖有 $n$ 個節點

### 方法一 : 用矩陣計算邊數
鄰接矩陣總共有 $n^2$ 個元素，每個元素都代表行與列是否有邊相連。由於圖不存在自環，扣掉自環的邊數有 $n$ 條邊。因矩陣是對稱的，$r$ 連到 $c$ 與 $c$ 連到 $r$ 其實是相同一條邊，所以最後要除 $2$。因此得到共有 $\cfrac{n^2-n}{2}=\cfrac{n(n-1)}{2}$ 條邊

### 方法二 : 算組合數
注意到每兩點之間必有一條邊，因此是 $C^{n}_{2}=\cfrac{n(n-1)}{2}$

## 鄰接串列 Adjacency List
有人稱這個為鄰接表，反正都一樣
### 說明
在這個資料結構裡面，我們只記錄兩節點的連接狀況，有邊就紀錄，沒邊就不理他。對於每個節點 $u$，鄰接串列只記錄 $u$ 有連到的節點 $v$。以下就給個圖，自行意會一下吧!

<center>
<img src="https://hackmd.io/_uploads/rk4W2LuDeg.png" style="margin: 0 auto; display: block; width: 400px">
</center>

### 程式實作
傳統上應該要用 linked list，但是因為這是競程筆記，所以我們還是用一些 vector 把他們都串起來就好。實際上，這算是一個二維陣列，只是因為 vector 可以調整大小、插入元素的緣故，因此這樣存就相當於用 linked list 存，效果差不多，只是空間可能會大一點，但還是跑得動

```cpp
int n = 50; // 節點數
vector<int> g[n];
```

若我們想要存入上面的例子，那可以做以下的操作
```cpp
g[1].push_back(2), g[1].push_back(4);
g[2].push_back(1), g[2].push_back(6);
g[3].push_back(5), g[3].push_back(6);
g[4].push_back(1), g[4].push_back(5);
g[5].push_back(3), g[5].push_back(4), g[1].push_back(6);
g[6].push_back(2), g[6].push_back(3), g[6].push_back(5);
```

以上例子是無向圖，如果是有向圖的話，可以自己想想看

## 儲存帶權有向圖
有時候，我們要儲存的對象可能不是單純的有向 / 無向圖，像是若要計算兩點最短距離，那可能會在邊上賦值。圖上附加其他屬性的例子百百種，所以我們很常需要配合其他的資料結構來儲存圖的附加屬性

### 點權
由於在電腦中，節點都是有編號的，因此一個一維陣列就足夠了

其他像是度數等性質也都是這樣完成儲存

### 邊權
通常邊權在數學上的定義是 $f:E\rightarrow \mathbb{R}$，但是在競程通常只會碰整數，所以是 $f:E\rightarrow \mathbb{Z}$，但是這要如何儲存呢? 直觀上，從鄰接矩陣的定義來說，開一個二維陣列就可以解決，但是往往我們都是用鄰接串列來存才能避免用到太大的空間。因此我們只需要在鄰接串列上附加一個空間專門來存邊權即可

在實作上我們可以用 pair 來解決，剩下都一樣

```cpp
typedef pair<int, int> pii;
vector<pii> vec[N];  // vec[u] = {v, w}: u 為起點, v 為終點, w 為路權
```

但凡事必有例外，像是 Floyd-Warshall 演算法就必須使用二維陣列 (矩陣) 來實作，而非鄰接串列

## 邊陣列 Edge Array
不難發現其實一條邊其實就兩個終點而已，頂多再加上邊權，因此可以考慮直接開一個 pair / struct 陣列把所有邊的資訊儲存起來。要注意的是這種儲存方法並不適合遍歷。在 [Bellman-Ford 演算法](https://hackmd.io/@ShanC/Bellman-Ford-Algorithm)時會用到這種儲存方法

### 無權邊
```cpp=
pair<int, int> edges[MXN];   // 這裡儲存邊的兩個終點
for(int i = 0; i < m; i++){  // 輸入可以這樣處理
    cin >> edges[i].first >> edges[i].second;
}
```
### 帶權邊
```cpp=
struct Edge{                 // 儲存兩終點 u, v 與邊的權重 w
    int u, v, w;
}edge[MXN];
for(int i = 0; i < m; i++){  // 輸入可以這樣處理
    cin >> edge[i].u >> edge[i].v >> edge[i].w;
}
```

## 題目練習
[Atcoder abc_232 C - Graph Isomorphism](https://atcoder.jp/contests/abc232/tasks/abc232_c) (圖同構裸題)

----

## 參考資料

- Introduction to Algorithms, Fourth Edition
- D.B.West - Introduction to Graph Theory 2/e

----

> 上一篇: [基礎圖論 (三)](https://hackmd.io/@ShanC/basic-graph-theory-3)

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/8/1