# Elementary Graph Algorithm 基本圖論
### Graph 圖

* Graph $G=(V,E)$
* $V:\text{頂點(vertex)的集合}$
* $E:\text{邊(edge)的集合}$
* Directed Graph 有向圖
* $E\text{ 由頂點「有序對」 }(u,v)\text{ 組成，且 }(u,v) \not=(v,u)$
* `self-loop` 是可以的，即 $u=v$
* Undirected graph 無向圖
* $E\text{ 由頂點「無序對」 }(u,v)\text{ 組成，且 }(u,v) =(v,u)$
* `self-loop` 是不可以的，即 $u \not= v$
* 圖示：

* Edge 邊
* 有向圖中 $(u,v)$ 邊：表示 $u$->$v$、$(v,u)$ 邊：表示 $v$->$u$
* 無向圖中 $(u,v),(v,u)$ 邊：表示同時連到頂點 $u$ , $v$
* 只要有Edge相連，就稱兩個頂點 `adjacent(相鄰)`

* Graph 的兩種表示法：
* adjacent list (相鄰串列)
* Graph 比較稀疏(sparse)時偏好用 `list`
* adjacent matrix (相鄰矩陣)
* Graph 比較稠密(dense)時偏好用 `matrix`
#
### Adjacent-List Representation 相鄰串列表示法

* 陣列 $A_{dj}$ 有 $|V|$ 個 `list` ，每個頂點一個
* $A_{dj}[u]$ 存放所有與 $u$ 相鄰的頂點
* 頂點通常以任意順序存放
* 適用於稀疏圖：$|E|\ll |V|^2$
* 總長度和：有向圖是 $|E|$，無向圖是 $2|E|$
* 優點：空間複雜度是 $\Theta(V+E)$
* 缺點：沒有辦法快速去判斷某條邊例如：$(u,v)$ 是否存在

#
### Adjacent-Matrix Representation 相鄰矩陣表示法
* 用一個大小為 $|V|\times|V|$ 的陣列紀錄相鄰 ，$A=a_{ij}$
* if $(i,j)\in E$ -> $a_{ij}=1,\ otherwise\ a_{ij}=0$
* 適合稠密(dense)的圖 => $|E|\text{ 接近 }|V|^2$
* 對於無向圖來說 $A=A^T$，因為 $(u,v),(v,u)$ 是同一條邊
* 優點：檢查兩點是否相連很容易，直接看 $a_{ij}$ 的時間複雜度是 $O(1)$
* 缺點：空間複雜度固定要求是：$Θ(V^2)$ 跟有多少條 `Edge` 無關
>無向圖：
>

>有向圖：
>

#
### Simplified BFS & DFS
#
### Breadth-First Search (廣度優先搜尋)
* 沿著邊探索，找出所有從來源點 $s$ 可到達的頂點
* 會先找到距離為 $k$ 的所有點，再找距離 $k+1$ 的點
* 距離： $s$ 到某點所需的最少邊數
* 會產生一棵以 $s$ 為根的 `BFS樹`，包含所有可達頂點
* 教材中的圖片會用顏色表示頂點的狀態
* 白色：未發現
* 灰色：已發現但尚未處理完鄰居(通常在Queue中)
* 黑色：鄰居都處理完
* $S$ 表示來源的頂點
* $d[u]$ 表示 $s$ 到頂點 $u$ 的距離
* $\pi[u]$ 是 $u$ 的前驅節點(父節點)，若沒有則 `NIL`
* $Q$ 表示用於存放灰色頂點(已發現但尚未處理完鄰居)的 `Queue`
* 時間複雜度 $O(V+E)$
* 虛擬碼執行流程：
* 
* $BFS(G,s)$ -> 從圖 $G$ 的 $s$ 當作起點開始
* 2~4行的for each在初始化，對 $s$ 以外的節點做：
* $color[u]=white$ 表示未被發現
* $d[u]=\infty$ 表示不知道怎麼從 $s$ 走到 $u$
* $\pi[u]=NIL$ 表示還沒有父節點

* 設定起點 $s$：
* $color[s]= GRAY \text{ 表示已被發現}$
* $d[s]=0 \text{ 起到到自己的距離是 } 0$
* $\pi[s]=NIL \text{ 起點沒有父節點}$
* 建立一個空的 `Queue` 把起點 $s$ 放進去

* 主迴圈：
* $Q \not=\emptyset$ -> 只要 `Queue` 中還有元素就不停
* $u \leftarrow DEQUEUE(Q)$ 取出當前 `Queue` 中最早進入的元素 $u$
* for each $v \in A_{dj}[u]$ 檢查 $u$ 的每個鄰居 $v$
* fo if $color[v]=white$ 只處理第一次被發現的點，避免無限迴圈
* 對第一次發現的點做狀態更改到 `GRAY`
* $d[v]\leftarrow d[u]+1$ 第一次到達 $v$ 一定是最短路徑，更新最短距離
* $\pi[v]\leftarrow u$ 紀錄父節點
* $ENQUEUE(Q,v)$ 把節點 $v$ 加入 `Queue` 當中，之後再展開它的鄰居
* 主迴圈結束後，把 $u$ 的狀態改為 `BLACK` 表示 BFS完成
* 示意圖 

#
### Shortest Paths 最短路徑
* 一條從 $s \text{ 到 }v$ 長度為 $𝛿(s,v)$ 的路徑
* 最短路徑指的是 $s$ 到 $v$ 的路徑中，邊數最短者 (BFS算出的$d[v]$)
* 不可抵達的話距離是 $\infty$
* $v$ 與 $u$ 相鄰的話，到 $v$ 的最短路徑$\le 𝛿(s,u)+1$
#
### Breadth-Firth Trees
> 把原先Graph $G$ 中BFS源點 $s$ 所有可抵達的頂點做成一棵樹，
> `root` $s$ 到樹中任意節點都是原先的最短路徑
#
### Depth-First Search $_I$
* Edges 會從最近的一個被發現，且仍有未探索出邊的頂點 $v$ 展開
* 當 $v$ 的邊都掃完後，就回溯到發現 $v$ 的那個頂點，繼續掃它剩下的邊
* 教材中顏色代表不同含意：
* 白色：未被發現
* 灰色：已發現未完成
* 黑色：已完成
* 時間複雜度：$O(V+E)$
* 虛擬碼 
* $d[u]$ 紀錄第一次被發現(變灰)的時間戳
* $f[u]$ 紀錄DFS檢查完 $u$，把 $u$ 狀態改為 `Black` 的時間戳
* $\pi[u]$ 紀錄父節點
* $u$ 在 $d[u]$ 的時間點前是 `White`，在 $d[u]$ $f[u]$ 之間的是 `Gray`，$f[u]$ 後是 `Black`
* 虛擬碼的流程：
* 主程式 DFS($G$)：
* 1~3行在初始化所有頂點
* 第4行建立了一個全域計時器，用來標記時間戳
* 開始對每個頂點 $v$ 進行拜訪
* DFS-VISIT($u$)：
* 1 被拜訪的節點標記為 `Gray`
* 2~3 更新時間，並記錄被發現的時間點到 $d[u]$
* 4 探索 $u$ 所有相鄰的頂點 $v$
* 5 如果發先頂點 $v$ 是 `Withe` 還未被發現
* 6 將父節點 $u$ 記錄到 $\pi[v]$ 當中
* 7 繼續向下探索進行拜訪 BFS-VISIT($v$)
* 8 代表 $u$ 的所有鄰居都處理完了，將 $u$ 標記 `Black` 準備回朔
* 9 更新時間再紀錄時間戳到 $f[u]$ 當中
* 流程示意圖 
#
### Properties of DFS

* 對於任意兩個頂點 $u,v$ 的區間 $[\;d[u],d[v]\;]\;,\; [\;d[v],d[u]\;]$ 來說只有三種關係：
* 兩個區間完全不相交 (彼此不是祖先\子孫)
* $u$ 的區間完全包含在 $v$ 的區間內 ($u$ 是 $v$ 的子孫)
* $v$ 的區間完全包含在 $u$ 的區間內 ($v$ 是 $u$ 的子孫)
* 如果 $v$ 是 $u$ 的子孫那 $d[u]<d[v]<f[v]<f[u]$
#
### Classification of Edges 邊的分類
* Tree edge
* $edge(u,v)$ 第一次發現 $v$ 時的邊
* Back edge
* $edge(u,v)$ 將 $u$ 連接到某個祖先 $v$ 的邊
* Forward edge
* $edge(u,v)$ 從 $u$ 連到 $u$ 的某個子孫 $v$，但不是樹邊
* Cross edge
* 其他的所有邊
* 定理22.10
* 在無向圖DFS中，每條邊不是Tree edge就是Back edge
* 引理22.11
* 在有像圖中是無環的(acyclic)，那麼若且唯若DFS是沒有back edges的
#
### Topological Sort 拓樸排序
* 把所有頂點線性排列，只要Graph中有一條邊 $u \rightarrow v$ 那麼排序中 $u$ 一定會在 $v$ 前面
* 而且該Graph一定是dag (directed acyclic graph)
* 把排序後的頂點依序畫在一條水平線上每條邊都必須是左邊指向右邊
* $v_1\rightarrow v_2\rightarrow v_3\rightarrow ...\rightarrow v_n$
* 時間複雜度：$O(V+E)$
* 虛擬碼&講解：
* 
* 呼叫DFS來計算出每個頂點的完成時間 $f[v]$
* 一旦該頂點完成後馬上把它插入進 `linked list` 的最前端
* 回傳這個由頂點組成的鏈表
#
### Strongly Connected Components and Graph

* Strongly Connected Components (SCC)
* 一個由最大互通頂點組成的集合 $C$ 是全部頂點組成的集合 $V$ 的子集合
* 對於集合 $C$ 內的任意兩點 $u ,v$要可以互通

* Strongly connected directed graph
* 整張Graph中任意兩點都能互相到達
* 友且只有一個SCC，就是整張圖自己本身
* SSC示意圖：
#
### Decomposing a Directed Graph

* Transpose of directed graph (轉置圖)
* $G^T=(V,E^T)$
* $E^T=\{\; (u,v):(v,u)\in E \;\}$
* 將原本 $G$ 的所有邊反過來
* Component Graph
* $G^{SCC}=(V^{SCC},E^{SCC})$
* $V^{SCC}=\{\; v_1,v_2,...,v_k \;\}$
* 每一個 $v_i$ 代表圓凸的一個 SCC $C_i$
* 原圖 $G\;中若存在\ x→y,\ x∈C_i,\ y∈C_j,\ i\not=j$ 那 $G^{SCC}$ 中就有 $(V_i,V_j)$ 這條邊

* 演算法虛擬碼&流程：
* 1 呼叫DFS 得到每個頂點 $v$ 的完成時間
* 2 將Graph進行轉置
* 3 將 $G^T$ 做DFS，且起點順序必須是 $f[u]$ 由小到大
* 4 將第3行中每次做DFS得到的DFS樹輸出就是一個SCC

* 時間複雜度：$Θ(V+E)$
* 流程示意圖