# 圖論 II
WiwiHo
---
https://hackmd.io/@wiwiho/crc1082algo
https://tg.pe/xgaG
![](https://i.imgur.com/KqGWkCw.png)
---
# 有向無環圖
---
## 拓樸排序
Topological sort
----
若從節點 $u$ 能到達節點 $v$
在拓樸排序中 $u$ 就要出現在 $v$ 之前
----
### Kahn's algorithm
----
不斷把入度 0 的節點拔掉
Note:
講實作細節
----
### DFS
----
DFS 的出點順序反過來就是拓樸排序
Note:
講證明
舉不是 DAG 會不成立的例子
講還可以順便判環
---
## DAG DP
----
把 DP 的每個狀態視為節點
若 $u$ 是 $v$ 的轉移來源
就連有向邊 $(u,v)$
圖會是 DAG
----
反過來
DAG 上當然可以 DP
Note:
講 DAG 最長路徑
畫圖
---
# 最短路徑
----
- 單點源:求某個起點到其他所有點的最短路徑
- 全點對:求所有點對的最短路徑
Note:
講多點源
----
## 負環
在負環上一直繞
路徑長就會一直變短
所以有負環就不存在最短路徑
----
## 性質
最短路徑必是簡單路徑
Note:
口頭講原因
---
## 鬆弛
Relaxation
----
對邊 $(u,v)$ 鬆弛:
用到 $u$ 的最短路徑更新到 $v$ 的最短路徑
----
對點 $v$ 鬆弛:
對 $v$ 的所有臨邊或出邊鬆弛
---
## Dijkstra's algorithm
----
還記得 BFS 嗎?
Note:
講為什麼 BFS 可以做最短路徑
----
邊帶權會造成
直接把點丟在 queue 尾端
會無法滿足距離遞增
----
那就用 priority queue?
----
一開始所有 $dis_v$ 都是未確定的
當確定一個 $dis_v$ 時,就鬆弛 $v$
----
如果權重都不是負的
已知最小的未確定的 $dis_v$ 肯定不能再變小了
就確定它
----
```cpp
vector<vector<pair<int, int>>> g; //鄰接串列,pair 是 (邊權, 邊到達的點)
//別忘了改成從小到大排序,pair 是 (dis_v, v 的編號)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
vector<int> dis; //先初始化好 dis[s]=0,其他 dis[v]=很大的數字
while(!pq.empty()){
int now = pq.top().second;
int d = pq.top().first;
pq.pop();
if(d != dis[now]) continue;
for(pair<int, int> i : g[now]){
if(d + i.first < dis[i.second]){
dis[i.second] = d + i.first;
pq.push(make_pair(d + i.first, dis[i.second]));
}
}
}
```
Note:
特別注意檢查 d == dis[now]
----
時間複雜度:$O((|V|+|E|) \log |E|)$
---
## Floyd-Warshall algorithm
----
全點對最短路徑?
----
做 $|V|$ 次 Dijkstra's algorithm?
速度快但不能做負權邊
----
$dis_{i,j}=\min\{dis_{i,k}+dis_{k,j}| k \neq i,j\}$
----
轉移順序?
有狀態互為轉移來源
----
$dis_{k,i,j}=$
由前 $k$ 個節點和 $i$、$j$ 為兩端點
構成的最短路徑長
----
$dis_{k,i,j}=\min(dis_{k-1,i,k}+dis_{k-1,k,j}, w_{i,j}, dis_{k-1,i,j})$
----
時間複雜度:$O(|V|^3)$
---
## Bellman-Ford algorithm/SPFA
----
有負權的單點源最短路徑?
Floyd-Warshall 可以做但浪費時間
----
最短路徑最多只有 $|V|-1$ 條邊
$\Rightarrow$ 把所有點都鬆弛 $|V|-1$ 次
如果還能鬆弛就是有負環
----
### SPFA
如果有節點在某一輪的距離沒有變
那下一輪就沒有必要再鬆弛一次
$\Rightarrow$ 每一輪記錄哪些節點距離改變
下一輪只鬆弛它們
另外記錄每個節點被鬆弛成功次數
超過 $|V|-1$ 就是有負環
---
## 最短路徑演算法的比較
----
![](https://i.imgur.com/TXJ6D2S.png)
---
# 並查集
Disjoint-set union-find
----
用來維護一些不相交的集合
支援:
- 將某兩個集合合併
- 查詢某個元素所屬的集合
----
將每個元素視為一個節點
集合看作一棵樹
讓集合中的其中一個點當根節點
----
### 合併
把其中一棵樹的根
變成另一棵的根的子節點
----
### 查詢
維護每個節點的父節點
遞迴找根
$\Rightarrow$ 可以判斷兩個點是否在同一集合
----
### 路徑壓縮
樹成鏈時
多次查詢同一個節點很浪費時間
$\Rightarrow$ 查詢完就把節點變成根節點的子節點
----
### 啟發式合併
把深度大的樹接到深度小的樹下
合併完深度會比反過來接大
$\Rightarrow$ 維護深度
----
### 時間複雜度
- 只有路徑壓縮:均攤 $O(n + f \log_{2+\frac{f}{n}}n)$
- 只有啟發式合併:單一操作 $O(\log n)$
- 都有:均攤 $O(m \alpha (n))$
Note:
$f=$ 查詢次數
$n=$ 元素數
$m=$ 操作總數
---
# 最小生成樹
----
## Prim's algorithm
Note:
畫圖講過程
----
## Kruskal's algorithm
Note:
畫圖講過程
---
# 最低共同祖先
Lowest common ancestor
----
如果 $u$ 是 $v$ 的祖先
那麼 $u$ 就是 LCA
----
否則
令 $w$ 為 $u$ 的祖先中
深度最小且不為 $v$ 的祖先的
令 $x$ 為 $w$ 和 $u$ 之間的邊數
----
$u$ 往上跳 $2^k$ 個節點到達的點記為 $anc(u, k)$
----
不斷找最大的 $k$
使得 $anc(u, k)$ 不是 $v$ 的祖先
把 $u$ 往上跳 $2^k$ 個節點
最後答案是 $anc(u, 0)$
----
## 蓋 anc
$anc(u,k)=anc(anc(u,k-1),k-1)$
----
## 判斷是否是祖先
子孫會比祖先晚入點、早出點
$\Rightarrow$ 記錄每個節點的入出點順序
{"metaMigratedAt":"2023-06-15T09:43:08.216Z","metaMigratedFrom":"YAML","title":"圖論 II","breaks":"false","contributors":"[{\"id\":\"02353542-5acb-4a66-abd0-128b1af24abb\",\"add\":3381,\"del\":9}]"}