# 圖論 I WiwiHo --- https://hackmd.io/@wiwiho/crc1082algo https://tg.pe/xgaG  --- # 基本概念與術語 --- ## 圖 Graph ---- ❌圖片（picture） ⭕圖（graph） ---- 由一些節點和邊組成的東西  ---- ### 圖的組成 - 節點（vertex）的集合 $V$ - 邊（edge）的集合 $E$ 記作 $G=(V,E)$ ---- ### 邊 連接兩個節點 ---- #### 無向邊 (undirected edge) 雙向的邊 連接節點 $u$、$v$ 的無向邊 記作 $(u,v)$、$(v,u)$ 且 $(u,v)=(v,u)$ i.e. 記作無序對 ---- #### 有向邊 (directed edge) 單向的邊 從 $u$ 到 $v$ 的有向邊 記作 $(u,v)$ i.e. 記作有序對 ---- - 只有無向邊的圖：無向圖（undirected graph） - 只有有向邊的圖：有向圖（directed graph） - 都有：混合圖 ---- #### 權重 邊或點上可能有權重 有就稱為帶權  ---- ### 圖上的東西 Note: 畫圖講 ---- ### 特殊圖 Note: 畫圖講 --- ## 樹 ---- 沒有環的連通圖  ---- ### 性質 - $|V|=|E|+1$ - 任兩點之間只有唯一一條簡單路徑 - 刪除任何一條邊後，就會變得不連通 - 加入任何一條邊，就會形成環 ---- ### 有根樹 ---- 無根樹上的任何一個節點都可以當作根 變成有根樹 ---- #### 有根樹上會出現東西 Note: 畫圖講 ----  --- # 儲存 --- ## 鄰接矩陣 ---- 一個 $|V| \times |V|$ 的矩陣 記作 $M$ $M_{u,v}$ 是邊 $(u,v)$ 的資訊 e.g. 存不存在、權重 ---- 空間複雜度：$O(|V|^2)$ 時間複雜度： - 加刪邊：$O(1)$ - 枚舉某一點的鄰邊或出邊：$O(|V|)$ ----  $M=\begin{bmatrix} \text{X} & 10 & \text{X} & 2 & 5 \\ 10 & \text{X} & 7 & 3 & \text{X} \\ \text{X} & 7 & \text{X} & \text{X} & \text{X} \\ 2 & 3 & \text{X} & \text{X} & \text{X} \\ 5 & \text{X} & \text{X} & \text{X} & \text{X} \end{bmatrix}$ Note: 注意無向圖和重邊 --- ## 鄰接串列 ---- 開 $|V|$ 個大小可變的容器 第 $i$ 個存節點 $i$ 的鄰邊或出邊資訊 ---- 空間複雜度：$O(|V|+|E|)$ 時間複雜度： - 加邊：元素加入容器的複雜度 - 刪邊：元素從容器移除的複雜度 - 枚舉某一點的鄰邊或出邊：遍歷容器的複雜度 - 枚舉所有點的鄰邊或出邊：均攤 $O(|V|+|E|)$ --- ## 鄰接矩陣和鄰接串列的比較 ---- ### 空間複雜度 鄰接矩陣：$O(|V|^2)$ 鄰接串列：$O(|V|+|E|)$ ---- ### 時間複雜度  --- ## 樹的儲存 ---- 1. 用一般圖的方式存 2. 只存父節點 3. 只存子節點 --- # 遍歷 --- ## 深度優先搜尋 Depth-First Search ---- 盡量往深處走 Note: 畫圖講過程 ---- 某種遞迴 ```cpp vector<vector<int>> g; //鄰接串列 vector<bool> vst; //用來記錄每個點走過了沒 void dfs(int now){ vst[now] = true; //do something for(int i : g[now]){ if(vst[i]) continue; dfs(i); } //do something } ``` ---- 呼叫 $dfs(v)$ $\Rightarrow$ $v$ 入堆 $\Rightarrow$ $v$ 入點 $dfs(v)$ 結束 $\Rightarrow$ $v$ 出堆 $\Rightarrow$ $v$ 出點 ---- 入點順序：前序 出點順序：後序 ---- 時間複雜度：$O(|V|+|E|)$ --- ## 廣度優先搜尋 Breadth-First Search ---- 先把所有知道可以走的點走完 Note: 畫圖講過程 ---- ```cpp vector<vector<int>> g; //鄰接串列 vector<bool> vst; //某個點有沒有走過或有沒有在 queue 裡 queue<int> q; q.push(...); //把起點放進去 while(!q.empty()){ int now = q.front(); q.pop(); for(int i : g[now]){ if(vst[i]) continue; q.push(i); vst[i] = true; } } ``` Note: 注意 vst ---- ### BFS 的順序 由起點開始擴散 https://www.youtube.com/watch?v=x-VTfcmrLEQ ---- 離起點進的先、離起點遠的後 $\Rightarrow$ 可以拿來做不帶權圖最短路徑 Note: 畫圖講 ---- 時間複雜度：$O(|V|+|E|)$ --- # 一些圖上的經典問題 更經典的下一堂課才會講 (? --- ## 表格上的問題 ---- $N \times M$ 的二維表格可以視為 有 $N+M$ 個節點的圖 如果某兩個格子可以互通 那就在它們兩個的節點之間連邊 ---- 小技巧： 通常能互通的格子相對位置是固定的 所以直接去看相對位置就好 ----  Note: 這題最短路徑長是含起終點的格子數 ---- 不帶權最短路徑 $\Rightarrow$ BFS --- ## 歐拉路徑 Euler path ---- 一條經過所有的邊 且不經過重複的邊 但可以經過重複的點的路徑 ---- ### 有歐拉路徑的條件 無向圖： 恰有 0 個或 2 個度數是奇數的點 有向圖： 所有點的入度等於出度 或有恰一個點的入度比出度多 1 和恰一個點的出度比入度多 1 ---- ### 求歐拉路徑 對邊 DFS 再把出點順序倒過來 --- ## 漢米爾頓路徑 Hamiltonian path ---- 經過所有點恰一次的路徑 （起終點相同不算重複） ---- 位元 DP Note: 看講義 講旅行推銷員 --- ## 藏在問題裡的圖 ---- 有時候題目裡不會出現任何關於圖的關鍵字 看起來也沒有類似點、邊的東西 但解法卻和圖論有關 ----  Note: 口頭講作法 ----  Note: 口頭講作法 --- # 一些樹的經典問題 --- ## 樹直徑 ---- 在樹上最長的簡單路徑 ---- ### 作法 先隨便找一個點 $u$ 找到離它最遠的點 $v$ 再找到離 $v$ 最遠的點 $w$ $v$ 到 $w$ 的簡單路徑就是樹直徑 ---- 兩次 DFS ---- ### 樹圓心 以它為根時 樹的深度會最小的點 Note: 會在直徑上 --- ## 樹重心 ---- 把一個節點 $v$ 從樹上拔掉 出現的連通塊大小都不超過本來點數的一半 $v$ 就是樹重心 ---- ### 性質 Note: 看講義，口頭講 --- # 二元樹 ---- 每個節點最多只有兩個子節點的有根樹 ---- 有時候子節點會有左右之分 Note: 講左右子節點、子樹、兄弟節點 ---- ## 性質 - 深度 $i$ 的節點最多有 $2^i$ 個。 - 深度 $i$ 的二元樹最多有 $2^{i+1}-1$ 個節點。 Note: 講證明 ---- ## 特殊的二元樹 Note: 看講義講 ---- ## 二元樹的儲存 ---- 1. 用一般圖或樹的存法 2. 只存左右子節點 ---- ## 二元樹的遍歷 ---- ```cpp //l[i]=i的左子節點，r[i]=i的右子節點，-1表示沒有 vector<int> l, r; void dfs(int now){ //preorder if(l[i] != -1) dfs(l[i]); //inorder if(r[i] != -1) dfs(r[i]); //postorder } ``` Note: 中序性質口頭講