---
tags: 圖論, 拓樸排序 Topological order, 最短路徑, 最小生成樹 MST, dfs tree, ap, bridge, scc
---
# 圖論
## 拓樸排序 Topological order

digraph topological1{
    nodesep=0.5
    rankdir = LR;
	a -> b[color = red];
    b -> e[color = orange]
    a -> d[color = red];
    d -> e[color = yellow];
    b -> c[color = orange];
    c -> e[color = green];
    e -> f[color = green];
    c -> f[color = blue];
}

### 方法1. 計算 in-degre
1. 將每一點的入度數算出
2. 入度數為0的點push進queue裡面
3. 將queue裡點的點拿出並將邊刪除
4. 刪除邊後的點入度數若為0則push進去queue
5. queue pop的順序為一組topological order
6. 若有結束後有入度數不為0的代表有環

### 方法2. dfs
* dfs未完成前又回到原dfs的點則圖有環
* dfs的過程為ㄧ組topological order
---
## 單源最短路徑

graph shortest_path{
    nodesep=1
    rankdir = LR;
    a -- b [label = "1"];
    a -- c [label = "2", color = green];
    b -- c [label = "4"];
    b -- d [label = "7"];
    c -- d [label = "4"];
    d -- e [label = "1"];
    c -- e [label = "3", color = green];
}

### 方法1. Bellman-Ford
#### 適用情形：
* 有負邊
* 檢測負環
#### **init:**
$\qquad$$edges = {(u_1, v_1), (u_2, v_2), (u_3, v_3), ... (u_m, v_m)}$
$\qquad$$d[n]={\infty}, d[start]=0$

#### **solve:**
$\qquad$ $for\:vertex=1\sim n:$
$\qquad$$\qquad$$for(u,v)\;in\;edges$
$\qquad$$\qquad$$\qquad$$d[vertex]=min(d[vertex],\:d[vertex]+cost(u,v))$ "鬆弛邊"
#### $複雜度O(nm)$

### 方法2. Dijkstra
#### 適用情形：
* 無負邊
* 時間限制較緊

#### **init:**
$\qquad$$d[n]=\infty,d[start]=0$

#### **solve:**
1. 將start點push進priority queue
2. 將top點依序拿出，連接的點若可更新權重，則更新為d[start]+cost，並push進priority queue
3. priority queue內為空則結束
#### $複雜度O(mlogm)$
---
## 多源最短路徑
### Floyd-Warshall
#### **solve:**
$\qquad for\:k=1\sim n:$
$\qquad\qquad for\ i=1\sim n:$
$\qquad\qquad\qquad for\ j=1\sim n:$
$\qquad\qquad\qquad\qquad dp[i][j]=min(dp[i][j],\ d[i][k]+dp[k][j])$

#### $複雜度O(n^3)$
---
## 並查集 disjoint-set

int Find(int x, vector<int> &parent){
    if(parent[x] == x){
        return x;
    }
    else{
        return parent[x] = Find(parent[x], parent);
    }
    
}

void Union(int x, int y, vector<int> &parent){
    parent[Find(x, parent)] = Find(y, parent);
    return;
}

### 路徑壓縮
* $parrent[Find(x)] = Find(y)$
* 複雜度:$O(log^*n)$
### 啟發式合併 union by rank
* rank: size of tree

---
## 最小生成樹 MST

graph MST{
    nodesep=1
    rankdir = LR;
    a -- c [label = "2", color = green];
    a -- b [label = "1", color = green];
    b -- c [label = "4"];
    c -- d [label = "4", color = green];
    b -- d [label = "7"];
    c -- e [label = "8"];
    d -- e [label = "3", color = green];
    e -- f [label = "6"];
    d -- f [label = "3", color = green];
}

### 方法1. kruskal
1. 將邊的cost由小到大排序
2. 將邊上的點依序Union，若已為同一群則忽略
3. $ans=\sum沒被忽略的邊$
#### $複雜度O(mlogm)$

### 方法2. prim
#### **init:**
$\qquad$$d[n]=\infty,d[start]=0$

1. 隨機挑選start點加入 priority queue
2. 將top點依序拿出，連接的點若可更新權重，則更新為cost，並push進priority queue
3. priority queue內空則完成
4. $ans = \sum_{i=1}^{n}d[n]$
#### $複雜度O(mlogm)$
---
## dfs tree

digraph dfs_tree{
    nodesep=0.5
    //rankdir = LR;
    a[color = red]
    c[color = red]
    b[color = red]
    i[color = red]
    d[color = red]
    j[color = red]
    a -> c
    a -> b[color = orange]
    b -> e[color = orange]
    b -> j
    j -> k
    j -> l[color = orange]
    c -> d[color = orange]
    c -> i
    d -> f[color = orange]
    i -> g
    i -> h[color = orange]
    i -> a[color = blue]
    g -> a[color = blue]
    k -> b[color = blue]
}

$t(u):進入u的時間$
$low(u):u最多經過一條backedge，可以走到的最小t值$
### bridge

digraph bridge{
    v
    u -> v[label = "bridge", color=orange]
}

$如果\ low(v)=t(v),\ 則u\rightarrow v為bridge$
### Articulation Point
#### Case1 $點u不是root$

graph case1{
    o[label=""]
    u[color=red]
    o -- u
    u -- v
}

$如果low(v)\ge t(v),\ 則點u為AP$
#### Case2 $點u是root$

graph case2{
    u[color=red]
    u -- v1
    u -- v2
}

$如果low(v_1)\ge t(v),\ 且low(v_2)\ge t(v),\ 則u為AP$

---
## 強聯通單元 SCC

digraph scc{
    nodesep=0.5
    rankdir = LR;
    b -> d
    b -> e
    d -> e
    a -> g
    b -> g
    subgraph cluster0{
        label="scc1";
        color=green;
        shape=circle;
        a -> b[color=orange];
        b -> c[color=orange];
        c -> a[color=orange];
    }
    subgraph cluster1{
        color=green
        label="scc2"
        d
    }
    subgraph cluster3{
        color=green
        label="scc3"
        e -> f[color=orange]
        f -> g[color=orange]
        g -> e[color=orange]
    }
}

### 性質
* 若將每一組scc視作一節點，則此圖必為DAG
* $如果sccA\rightarrow sccB$
$則max\{t(a)|a\in A\}>max\{t(b)|a\in B\}$

---