# 圖論 (2) ## 6/7 社課 ---- ## Outline - 圖的遍歷 - 拓撲排序 --- ## 圖的遍歷 以某種方式走過圖上所有的點 ---- ## DFS 深度優先搜尋 每走到一個點，就看這個點能不能繼續走下去 如果可以，就直接走，否則回到上一個點 [圖例](https://img-blog.csdnimg.cn/20200308153152672.gif) ---- ## DFS 的用處 - 好寫方便的遍歷方式 - 解決相鄰兩點的問題 ---- ## DFS 的實作 - 直接遞迴 - 紀錄一個 `visited` 陣列，表示某個點是否走過 - 每走到一個點，若沒走過就繼續 DFS 下去 ---- **範例 Code** ```cpp= const int MAXN=2e5+5; vector<int> e[MAXN]; // 存圖 bool visited[MAXN]; // 紀錄是否走過 void dfs(int cur){ visited[cur]=true; // 每到一個點，就把狀態設為走過 for(int v:e[cur]){ // 看所有與之相鄰的點 if(visited[v]) continue; // 若已經走過某個點就跳過他 dfs(v); // 沒走過就 DFS 下去 } } ``` ---- **備註** ```cpp= vector<int> v1; vector<char> v2; for(int i:v1){ // 可以遍歷所有在 v1 中的元素 // ... } for(char i:v2){ // ... } ``` ```cpp= // 可以用在各種 STL 上 set<int> s; map<int, int> mp; for(int i:s){ // ... } for(pair<int, int> i:mp){ // ... } ``` ---- ## BFS 廣度優先搜尋 可以想像在迷宮中倒下一個水流 水流一定會先往離他進的格子流 BFS 就是每走到一個點 依次走完所有與之相鄰的點，才走到下一層 [圖例](https://img-blog.csdnimg.cn/20200308151345758.gif) ---- ## BFS 的用處 - 越近的點越早遍歷到 - 解決不帶權最短路徑 ---- ## BFS 的實作 - 實作一個 queue，表示準備遍歷的點順序 - 每到一個點就把所有與之相鄰的點推入 queue - 一樣要記錄 `visited`，表示已經走過的點 - 紀錄走過的時間和 DFS 不太一樣 - 要在遇到時就紀錄 ---- **範例 Code** ```cpp= const int MAXN=2e5+5; vector<int> e[MAXN]; // 存圖 bool visited[MAXN]; // 記錄是否走過 void bfs(int start){ queue<int> q; // 紀錄接下來要走哪些點 q.push(start); // 先推入第一個點 visited[start]=true; // 要記得改狀態 while(!q.empty()){ // 重複直到連通圖遍歷完 int cur=q.front(); // 先把這個點拿出來，比較好操作 q.pop(); // 把他從 queue 當中移除 for(int v:e[cur]){ // 看所有與之相鄰的點 if(visited[v]) continue; // 若已經走過某個點就跳過他 q.push(v); // 沒走過就推入 queue visited[v]=true; // 記得改狀態 } } } ``` ---- ### [迷宮問題#1](https://zerojudge.tw/ShowProblem?problemid=a982) 給定 $N\times N$ 的迷宮 `#` 代表障礙物， `.` 代表路 一開始在點 $(2,2)$ 的位置，要走到 $(N-1, N-1)$ 求最短路徑長 ---- 直接用 BFS 的想法做？ 每到一個點，看他的上下左右能不能走 能走就推進 queue ---- 這樣是最短沒錯 啊我要怎麼知道他有多長？ ---- 多推一個東西到 queue 裡面！ 每推入一個點的同時，紀錄他和原點的距離是多少 可以用 pair 或是 struct 實作 ---- ### 實作細節 每次枚舉相鄰點的時候 不用一個一個 $(x, y+1),(x, y-1),\cdots$ 可以做一個 dx, dy 的陣列 表示每一個方向要前進的距離 ---- **Code** ```cpp= #include<bits/stdc++.h> using namespace std; int n, ans=0; char point[105][105]; bool v[105][105]; int dx[4]={1, -1, 0, 0}, dy[4]={0, 0, 1, -1}; // 有四個方向 struct st{ // 把一個點的資訊包成 struct int x, y, len; }; void bfs(int x, int y){ queue<st> q; q.push(st({x, y, 1})); // 一開始在 (x, y)，距離為 0（題目原因為 1） while(!q.empty()){ st cur=q.front(); q.pop(); for(int i=0; i<4; i++){ // 枚舉四個方向的相鄰點 if(!v[cur.x+dx[i]][cur.y+dy[i]]){ v[cur.x+dx[i]][cur.y+dy[i]]=1; if(cur.x+dx[i]==n-1&&cur.y+dy[i]==n-1){ ans=cur.len+1; // 若走得到終點，就更新答案 return; } // 是 `.` 才能走 if(point[cur.x+dx[i]][cur.y+dy[i]]=='.') q.push({cur.x+dx[i], cur.y+dy[i], cur.len+1}); // 記得更新路徑長度 } } } } int main(){ cin >> n; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin >> point[i][j]; bfs(2, 2); if(ans) cout << ans << '\n'; else cout << "No solution!" << '\n'; // ans=0 表示走不到 } ``` ---- ### [圖論之二分圖測試](https://tioj.ck.tp.edu.tw/problems/1209) 給定一個 $N$ 個點 $M$ 條邊的圖 看是否有辦法將點分成兩堆 使得同一堆當中所有點之間都不能有邊 ---- **將題目轉換一下** 問是否有辦法將兩種顏色塗到所有點上 使得相鄰兩點的顏色皆不相同 ---- 每到一個點 將這個點塗成和前一個點不同的顏色 如果出現了矛盾 也就是現在所在的點和遍歷下去的點同色 就不是二分圖 BFS 和 DFS 都可以做 --- ## 拓撲排序 將點以某種神奇的方法排序 ---- ### 名詞定義 無向圖：所有邊都沒有方向，只表示他連著兩點 有向圖：所有邊都有方向，表示從某點連至某點 環：可以從某個點經過別的點回到自己的路徑 ---- ### 名詞定義 對於一個點，他的： - 度數：這個點連接了多少條邊 - 出邊：以這個點作為起點的邊 - 入邊：以這個點作為終點的邊 - 出度：出邊有多少條 - 入度：入邊有多少條 ---- ### 有向無環圖（DAG） 顧名思義 他是一個有向圖，但他沒有環 拓撲排序就是在對他操作 ---- 想想排序要幹嘛？ **按照某種特定方式排列** **讓我們比較好做事** ---- 那拓撲排序在幹嘛？ **把點做排序** **讓每條邊的起點一定排在終點的前面** 也就是走到一個點前，指向他的點一定要先都走過 ---- **學術一點** 將所有點排成一種序列 $v_1, v_2, \cdots, v_n$ 使得所有邊 $v_i\rightarrow v_j$，都有 $i<j$ 這種排序**可能不唯一** ---- 因為是 DAG，所以一定有入度為 $0$ 的點 他們就會在拓撲排序的最前面 將入度為 $0$ 的點放入拓撲排序後 就把他從圖上拿掉，剩下的圖還會是 DAG 如此一來，就會產生新的入度為 $0$ 的點 ---- 因此可以開一個 `deg` 陣列 紀錄每個點的入度 接著開一個 queue 把所有入度為 $0$ 的點都放進去 從 queue 的最前面開始一個個加到拓撲排序裡 每加一個就將他的出邊刪掉，即出邊終點入度減一 重複做直到 queue 為空 就排好了！ ---- 如果 queue 為空了 但是還有點的入度不為 $0$？ 這些點從沒進過 queue 中 $\cdots$ **存在有向環！** 沒有拓撲排序 ---- [裸題](https://cses.fi/problemset/task/1679) **BFS 作法** ```cpp= #include<bits/stdc++.h> using namespace std; int n, m, deg[100005]; vector<int> e[100005], ans; queue<int> q; int main(){ cin >> n >> m; for(int i=0, u, v; i<m; i++){ cin >> u >> v; e[u].push_back(v); deg[v]++; // 紀錄入度 } for(int i=1; i<=n; i++) if(deg[i]==0) q.push(i); while(!q.empty()){ int now=q.front(); ans.push_back(now); // 拿出 queue 中的點 q.pop(); for(int i:e[now]){ deg[i]--; // 將這個點的出邊終點入度減一 if(deg[i]==0) q.push(i); // 若多一個入度為零的點，加入 queue } } if(ans.size()!=n) cout << "IMPOSSIBLE" << '\n'; else for(int i:ans) cout << i << ' '; } ``` ---- 拓撲排序也有 DFS 作法 主要的想法就是利用 DFS 會直接遍歷到最深處 可知最深處一定是拓撲排序的最後 類似的，DFS 離開點時 就可以將其加入拓撲排序的後面 最後將得到的序列反轉就是答案 ---- 關鍵字：時間戳記 **DFS 作法** ```cpp= #include<bits/stdc++.h> using namespace std; int n, m, vis[100005]; vector<int> e[100005], ans; void dfs(int now){ vis[now]=1; for(int i:e[now]){ if(vis[i]==2) continue; if(vis[i]==1){ cout << "IMPOSSIBLE" << '\n'; exit(0); } dfs(i); } ans.push_back(now); vis[now]=2; } int main(){ cin >> n >> m; for(int i=0, u, v; i<m; i++){ cin >> u >> v; e[u].push_back(v); } for(int i=1; i<=n; i++) if(!vis[i]) dfs(i); reverse(ans.begin(), ans.end()); for(int i:ans) cout << i << ' '; } ``` --- ### 排完了，然後呢？ ---- 融合 DP 試試看！ ---- ### [專案時程](https://tioj.ck.tp.edu.tw/problems/1717) 某個專案有 $N$ 個項目 某些項目要完成前置的項目才能進行 除了項目的先後順序外 第 $i$ 個項目需要花 $t_i$ 天完成 求完成所有項目的最少天數 $N\le 1000$ ---- #### 赤裸裸的 DAG！ 總之先拓撲排序再說 ---- 有了節點先後順序，可以來看看要怎麼做 注意到，某節點最早的**開始時間** 會是他所有入邊起點當中**最早完成時間最晚的** （因為要所有前置項目都完成才能進行） ---- 令 $dp[x]$ 代表第 $x$ 項目最早完成時間 則 $dp[x]=\displaystyle\max_{(i, x)\in E}{dp[i]}+t_x$ 即所有連到他的點當中最大的 加上他自己本身所需時間 ---- **Code** ```cpp= #include<bits/stdc++.h> using namespace std; int t, n; int main(){ cin >> t; while(t--){ cin >> n; vector<int> deg(n+1, 0); vector<int> w(n+1, 0); vector<int> e[n+1]; vector<int> dp(n+1, 0); for(int i=1, x; i<=n; i++){ cin >> w[i] >> x; for(int j=0, u; j<x; j++){ cin >> u; e[i].push_back(u); deg[u]++; } } queue<int> q; for(int i=1; i<=n; i++) if(!deg[i]) q.push(i); while(!q.empty()){ int now=q.front(); q.pop(); dp[now]+=w[now]; for(int i:e[now]){ dp[i]=max(dp[i], dp[now]); deg[i]--; if(!deg[i]) q.push(i); } } cout << *max_element(dp.begin(), dp.end()) << '\n'; } } ```