圖論 II - HackMD

--- tags: CRC --- # 圖論 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$ 記錄每個節點的入出點順序

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.