圖論 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:

中序性質口頭講