# 圖論(Graph Theory) 圖論（Graph Theory）是探討關於圖（Graph）這個數學模型的理論 主要目的是找到如何解決有關於圖（Graph）的問題 以下為圖的範例([source](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E5%AD%A6)#/media/File:6n-graf.svg))： ![image](https://hackmd.io/_uploads/H1R552Og-l.png =70%x) ## 圖的基本 ### 結構 圖是由**點（Node）** 與 **邊（Edge）** 所組成 通常以點儲存資料，邊有時會包含**權重（Weight）**，例如走這條邊所需的時間等等 生活中也常有圖的應用，例如家庭成員樹狀圖，其中的邊則代表直系親屬關係，點則表示人名等資訊 ### 類型 圖的類型根據邊（Edge）的性質而可先大致分成兩類：**有向圖**與**無向圖** * **有向圖（directed graph）**：例如 $A$ 可藉由 $\overrightarrow{AB}$ 通往 $B$ ，但 $B$ ==無法==回到 $A$ * **無向圖（undirected graph）**：例如 $A$ 與 $B$ 皆可藉由 $\overline{AB}$ 互通 --- * **有權重圖（weighted graph）**：邊上含有權重 * **無權重圖（unweighted graph）**：邊上無權重 （~~整段很像廢話~~） 另外現階段討論的圖大部分都屬於「**基本圖（simple graph）**，定義如下： 1. 不存在重邊（任兩點間只會有一條邊） 2. 不存在自連邊（不會有邊從自身出發到自身結束） 因此根據以上介紹，頁頂示例圖即為 ||<font color = "f00000">無權重無向圖</font>|| ### 其他名詞 #### 度數（degree） 此度數非彼度數，這裡的度數在無向圖中，指的是一個點上有==多少條邊==以自己作為端點； 在有向圖中，度數又分為 **入度（in-degree）** 和 **出度（out-degree）** * **入度（in-degree）**：有多少邊從==別的點==連到自身 * **出度（out-degree）**：有多少邊從==自身==連到別的點 ## 圖的儲存 最常用的儲存方式為使用**鄰接陣列 Adjacency Array**或**鄰接矩陣Adjacency Matrix** 儲存 將 $i$ 點可通往的點，儲存在`array[i]`中 > ps. 若一個點有很多資料要存，可使用不同的資料型態如`pair`或自訂`struct`（詳見：[struct](https://hackmd.io/@WLSH/rywX60IXWl)） 例如輸入 $a, \ b$ 兩點為一無權重==無向圖==中兩點連接，部分程式則可寫為 ```cpp vector<int> adj[SIZE]; ... int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a);//雙向 ``` 以此類推無權重==有向圖==（設 $a$ 走到 $b$）寫法為： ```cpp vector<int> adj[SIZE]; ... int a, b; cin >> a >> b; adj[a].push_back(b);//單向 ``` ## 圖的遍歷- <font color = "FF3F6F">無向圖</font> 有 $N$ 個點、 $M$ 條邊，每條邊連接 $A,\ B$ 兩點 問要從 $X$ 走到 $Y$ 需要幾步？ #### 輸入 第一行有兩個正整數 $N,\ M$，分別代表點與邊的數量，並保證 $1 \le N,\ M \le 100$ 接下來有 $M$ 行，每行有兩個正整數 $A、B$（$1 \le A,\ B \le N$），代表兩點互通 最後一行有兩個正整數 $X,\ Y$，代表要從 $X$ 走到 $Y$ #### 輸出 如果可以到達，則輸出一個正整數回答題目所求 反之輸出一個字串 $S$ = `Can't arrive!` #### 範例輸入1 ``` 4 3 1 2 3 2 3 4 1 4 ``` #### 範例輸出1 ``` 3 ``` #### 範例輸入2 ``` 7 8 1 2 4 3 6 7 3 6 2 4 7 5 1 3 1 5 1 7 ``` #### 範例輸出2 ``` 2 ``` #### 範例輸入3 ``` 3 1 1 2 1 3 ``` #### 範例輸出3 ``` Can't arrive! ``` ### BFS :::spoiler Sample Code ```cpp= #include <iostream> #include <vector> #include <queue> using namespace std; int used[105] = {0}, cnt[105] = {0}; int main(){ vector<int> adj[105]; int n, m; cin >> n >> m; for(int i = 0; i < m; i++){ int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } int x, y; cin >> x >> y; used[x] = 1; //bfs queue<int> q; q.push(x); while(!q.empty()){ int npos = q.front(); q.pop(); for(auto i : adj[npos]){ if(!used[i]){ cnt[i] = cnt[npos] + 1; used[i] = 1; q.push(i); } } } if(cnt[y] != 0) cout << cnt[y]; else cout << "Can't arrive!"; } ``` ::: ### DFS :::spoiler Sample Code ```cpp= #include <iostream> #include <vector> using namespace std; int used[105] = {0}, ans = INT_MAX; int x, y; vector<int> adj[105]; void dfs(int npos, int from, int cnt){ if(npos == y) {ans = min(ans, cnt); return;} for(auto i : adj[npos]){ if(i == from) continue; if(!used[i]){ used[i] = 1; dfs(i, npos, cnt + 1); used[i] = 0; } } } int main(){ int n, m; cin >> n >> m; for(int i = 0; i < m; i++){ int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } cin >> x >> y; used[x] = 1; //dfs dfs(x, -1, 0); if(ans == INT_MAX) cout << "Can't arrive!"; else cout << ans; } ``` ::: ## 圖的遍歷- <font color = "FF3F6F">有向圖</font> 有 $N$ 個點、 $M$ 條邊，每條邊連接 $A,\ B$ 兩點，==只能從 $A$ 到 $B$== 問要從 $X$ 走到 $Y$ 需要幾步？ #### 輸入 第一行有兩個正整數 $N,\ M$，分別代表點與邊的數量，並保證 $1 \le M \le N \le 100$ 接下來有 $M$ 行，每行有兩個正整數 $A、B$（$1 \le A,\ B \le N$），代表 $A$ 可通往 $B$ 最後一行有兩個正整數 $X,\ Y$，代表要從 $X$ 走到 $Y$ #### 輸出 如果可以到達，則輸出一個正整數回答題目所求 反之輸出一個字串 $S$ = `Can't arrive!` #### 範例輸入1 ``` 4 3 1 2 2 3 3 4 1 4 ``` #### 範例輸出1 ``` 3 ``` #### 範例輸入2 ``` 7 8 1 2 4 3 6 7 3 6 2 4 7 5 1 3 1 5 1 7 ``` #### 範例輸出2 ``` 3 ``` #### 範例輸入3 ``` 3 2 1 2 3 2 1 3 ``` #### 範例輸出3 ``` Can't arrive! ``` ### BFS :::spoiler Sample Code ```cpp= #include <iostream> #include <vector> #include <queue> using namespace std; int used[105] = {0}, cnt[105] = {0}; int main(){ vector<int> adj[105]; int n, m; cin >> n >> m; for(int i = 0; i < m; i++){ int a, b; cin >> a >> b; adj[a].push_back(b); //adj[b].push_back(a); } int x, y; cin >> x >> y; used[x] = 1; //bfs queue<int> q; q.push(x); while(!q.empty()){ int npos = q.front(); q.pop(); for(auto i : adj[npos]){ if(!used[i]){ cnt[i] = cnt[npos] + 1; used[i] = 1; q.push(i); } } } if(cnt[y] != 0) cout << cnt[y]; else cout << "Can't arrive!"; } ``` ::: ### DFS :::spoiler Sample Code ```cpp= #include <iostream> #include <vector> using namespace std; int used[105] = {0}, ans = INT_MAX; int x, y; vector<int> adj[105]; void dfs(int npos, int from, int cnt){ if(npos == y) {ans = min(ans, cnt); return;} for(auto i : adj[npos]){ if(i == from) continue; if(!used[i]){ used[i] = 1; dfs(i, npos, cnt + 1); used[i] = 0; } } } int main(){ int n, m; cin >> n >> m; for(int i = 0; i < m; i++){ int a, b; cin >> a >> b; adj[a].push_back(b); //adj[b].push_back(a); } cin >> x >> y; used[x] = 1; //dfs dfs(x, -1, 0); if(ans == INT_MAX) cout << "Can't arrive!"; else cout << ans; } ``` ::: ## 圖的遍歷- <font color = "FFFF">二維無向圖（$N$ * $M$方格圖）</font> 在某些題目中常見的二維陣列地圖，也是一種無權重無向圖。因此也可以使用BFS或DFS做遍歷，前面已經提過BFS，因此這裡僅說明DFS的遍歷 ### BFS [傳送門](https://hackmd.io/TMBfQGInTUSEfLEpLIaO_Q#BFS%E6%A6%82%E5%BF%B5%E8%AA%AA%E6%98%8E) ### DFS 根據DFS(深度優先搜尋)的概念，跟BFS淹水概念不同的地方是，DFS會選擇一條路走到底，直到不能走或到達終點才回到上一個分岔點找下一條路。 >[!NOTE]DFS(無向圖) 演示圖 >||(Source：https://zh-yue.wikipedia.org/wiki/File:Depth-First-Search.gif)|| >![image](https://upload.wikimedia.org/wikipedia/commons/7/7f/Depth-First-Search.gif) 可以用DFS的寫法去反推，因為我們到一個條件就會`return`，因此我們會退回上一格，若還有路可以走，則會選擇另一條路繼續「D」下去，以此類推直到`return`回起點 ### 實作 #### 輸入 第一行輸入一正整數 $N \leq 20$ 表示 $N * N$ 的地圖 接下來有 $N$ 行，每一行有 $N$ 個數字 $w_1,\ w_2,\ ...\ ,\ w_n \in (0, 1)$ $w_i = 0$ 代表該格不能通過 #### 輸出 輸出一個正整數 $s$ 代表從左上$(0,\ 0)$走到右下$(n-1,\ n-1)$的最短步數 ### 思路 可以用DFS的[排組](https://hackmd.io/gBH64XuxQ_SAcHhSxYgaXg#Zerojudge--e446-%E6%8E%92%E5%88%97%E7%94%9F%E6%88%90)寫法去反推，因為我們到一個條件就會`return`，因此我們會退回上一格，若還有路可以走，則會選擇另一條路繼續「D」下去，以此類推直到`return`回起點。 >記得要記錄`used`來判斷是否走過，在`return`後也要還原`used`狀態 >dfs帶著`cnt`走，找最小值 :::spoiler Code ```cpp= #include <iostream> using namespace std; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int n, mp[50][50], used[50][50], mn = INT_MAX; void dfs(int y, int x, int cnt){ if(y == n-1 && x == n-1){ mn = min(mn, cnt); return; } for(int i = 0; i < 4; i++){ int ny = y + dy[i], nx = x + dx[i]; if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue; if(used[ny][nx]) continue; if(mp[ny][nx] == 0) continue; used[ny][nx] = 1; dfs(ny, nx, cnt + 1); used[ny][nx] = 0; } } int main(){ cin >> n; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin >> mp[i][j]; } } dfs(0, 0, 0); cout << mn; } ``` :::