---
tags: CRC
---

# 圖論 I
WiwiHo

---

https://hackmd.io/@wiwiho/crc1082algo
https://tg.pe/xgaG

---

# 基本概念與術語

---

## 圖
Graph

----

❌圖片（picture）
⭕圖（graph）

----

由一些節點和邊組成的東西


----

### 圖的組成

- 節點（vertex）的集合 $V$
- 邊（edge）的集合 $E$

記作 $G=(V,E)$

----

### 邊

連接兩個節點

----

#### 無向邊
(undirected edge)

雙向的邊

連接節點 $u$、$v$ 的無向邊
記作 $(u,v)$、$(v,u)$
且 $(u,v)=(v,u)$

i.e. 記作無序對

----

#### 有向邊
(directed edge)

單向的邊

從 $u$ 到 $v$ 的有向邊
記作 $(u,v)$

i.e. 記作有序對

----

- 只有無向邊的圖：無向圖（undirected graph）
- 只有有向邊的圖：有向圖（directed graph）
- 都有：混合圖

----

#### 權重

邊或點上可能有權重
有就稱為帶權


----

### 圖上的東西

Note:

畫圖講

----

### 特殊圖

Note:

畫圖講

---

## 樹

----

沒有環的連通圖


----

### 性質

- $|V|=|E|+1$
- 任兩點之間只有唯一一條簡單路徑
- 刪除任何一條邊後，就會變得不連通
- 加入任何一條邊，就會形成環

----

### 有根樹

----

無根樹上的任何一個節點都可以當作根
變成有根樹

----

#### 有根樹上會出現東西

Note:

畫圖講

----


---

# 儲存

---

## 鄰接矩陣

----

一個 $|V| \times |V|$ 的矩陣
記作 $M$
$M_{u,v}$ 是邊 $(u,v)$ 的資訊
e.g. 存不存在、權重

----

空間複雜度：$O(|V|^2)$

時間複雜度：
- 加刪邊：$O(1)$
- 枚舉某一點的鄰邊或出邊：$O(|V|)$

----


$M=\begin{bmatrix}
\text{X} & 10 & \text{X} & 2 & 5 \\
10 & \text{X} & 7 & 3 & \text{X} \\
\text{X} & 7 & \text{X} & \text{X} & \text{X} \\
2 & 3 & \text{X} & \text{X} & \text{X} \\
5 & \text{X} & \text{X} & \text{X} & \text{X}
\end{bmatrix}$

Note:

注意無向圖和重邊

---

## 鄰接串列

----

開 $|V|$ 個大小可變的容器
第 $i$ 個存節點 $i$ 的鄰邊或出邊資訊

----

空間複雜度：$O(|V|+|E|)$

時間複雜度：
- 加邊：元素加入容器的複雜度
- 刪邊：元素從容器移除的複雜度
- 枚舉某一點的鄰邊或出邊：遍歷容器的複雜度
- 枚舉所有點的鄰邊或出邊：均攤 $O(|V|+|E|)$

---

## 鄰接矩陣和鄰接串列的比較

----

### 空間複雜度

鄰接矩陣：$O(|V|^2)$
鄰接串列：$O(|V|+|E|)$

----

### 時間複雜度


---

## 樹的儲存

----

1. 用一般圖的方式存
2. 只存父節點
3. 只存子節點

---

# 遍歷

---

## 深度優先搜尋
Depth-First Search

----

盡量往深處走

Note:

畫圖講過程

----

某種遞迴

vector<vector<int>> g; //鄰接串列
vector<bool> vst; //用來記錄每個點走過了沒

void dfs(int now){
    vst[now] = true;
    //do something
    for(int i : g[now]){
        if(vst[i]) continue;
        dfs(i);
    }
    //do something
}

----

呼叫 $dfs(v)$ $\Rightarrow$ $v$ 入堆
$\Rightarrow$ $v$ 入點

$dfs(v)$ 結束 $\Rightarrow$ $v$ 出堆
$\Rightarrow$ $v$ 出點

----

入點順序：前序
出點順序：後序

----

時間複雜度：$O(|V|+|E|)$

---

## 廣度優先搜尋
Breadth-First Search

----

先把所有知道可以走的點走完

Note:

畫圖講過程

----

vector<vector<int>> g; //鄰接串列
vector<bool> vst; //某個點有沒有走過或有沒有在 queue 裡

queue<int> q;
q.push(...); //把起點放進去

while(!q.empty()){
    int now = q.front();
    q.pop();
    for(int i : g[now]){
        if(vst[i]) continue;
        q.push(i);
        vst[i] = true;
    }
}

Note:

注意 vst

----

### BFS 的順序

由起點開始擴散

https://www.youtube.com/watch?v=x-VTfcmrLEQ

----

離起點進的先、離起點遠的後

$\Rightarrow$ 可以拿來做不帶權圖最短路徑

Note:

畫圖講

----

時間複雜度：$O(|V|+|E|)$

---

# 一些圖上的經典問題

更經典的下一堂課才會講 (?

---

## 表格上的問題

----

$N \times M$ 的二維表格可以視為
有 $N+M$ 個節點的圖
如果某兩個格子可以互通
那就在它們兩個的節點之間連邊

----

小技巧：
通常能互通的格子相對位置是固定的
所以直接去看相對位置就好

----


Note:

這題最短路徑長是含起終點的格子數

----

不帶權最短路徑

$\Rightarrow$ BFS

---

## 歐拉路徑
Euler path

----

一條經過所有的邊
且不經過重複的邊
但可以經過重複的點的路徑

----

### 有歐拉路徑的條件

無向圖：
恰有 0 個或 2 個度數是奇數的點

有向圖：
所有點的入度等於出度
或有恰一個點的入度比出度多 1
和恰一個點的出度比入度多 1

----

### 求歐拉路徑

對邊 DFS
再把出點順序倒過來

---

## 漢米爾頓路徑
Hamiltonian path

----

經過所有點恰一次的路徑
（起終點相同不算重複）

----

位元 DP

Note:

看講義
講旅行推銷員

---

## 藏在問題裡的圖

----

有時候題目裡不會出現任何關於圖的關鍵字
看起來也沒有類似點、邊的東西
但解法卻和圖論有關

----


Note:

口頭講作法

----


Note:

口頭講作法

---

# 一些樹的經典問題

---

## 樹直徑

----

在樹上最長的簡單路徑

----

### 作法

先隨便找一個點 $u$
找到離它最遠的點 $v$
再找到離 $v$ 最遠的點 $w$
$v$ 到 $w$ 的簡單路徑就是樹直徑

----

兩次 DFS

----

### 樹圓心

以它為根時
樹的深度會最小的點

Note:

會在直徑上

---

## 樹重心

----

把一個節點 $v$ 從樹上拔掉
出現的連通塊大小都不超過本來點數的一半
$v$ 就是樹重心

----

### 性質

Note:

看講義，口頭講

---

# 二元樹

----

每個節點最多只有兩個子節點的有根樹

----

有時候子節點會有左右之分

Note:

講左右子節點、子樹、兄弟節點

----

## 性質

- 深度 $i$ 的節點最多有 $2^i$ 個。
- 深度 $i$ 的二元樹最多有 $2^{i+1}-1$ 個節點。

Note:

講證明

----

## 特殊的二元樹

Note:

看講義講

----

## 二元樹的儲存

----

1. 用一般圖或樹的存法
2. 只存左右子節點

----

## 二元樹的遍歷

----

//l[i]=i的左子節點，r[i]=i的右子節點，-1表示沒有
vector<int> l, r;

void dfs(int now){
    //preorder
    if(l[i] != -1) dfs(l[i]);
    //inorder
    if(r[i] != -1) dfs(r[i]);
    //postorder
}

Note:

中序性質口頭講