圖論 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\) 肯定不能再變小了
就確定它

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\) 記錄每個節點的入出點順序