# 圖論 II WiwiHo --- https://hackmd.io/@wiwiho/crc1082algo https://tg.pe/xgaG  --- # 有向無環圖 --- ## 拓樸排序 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$ 就是有負環 --- ## 最短路徑演算法的比較 ----  --- # 並查集 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$ 記錄每個節點的入出點順序