圖論 - HackMD

--- tags: 教材 --- # 圖論 --- ## 目錄 - Introduction(簡介) - Example(範例) - Basic Algorithms(基本演算法) - Example(範例) - Advanced Topic(稍微進階的內容) --- ## Introduction ---- 圖 $G$ 由點 $V$ 與邊 $E$ 構成，記做 $G=(V,E)$ 。聽起來很難？ ---- 其實就是像這樣的東西 ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"->{"2" "3"} "1"->{"2" "4","0"} "2"->"3" "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` --- ## 線上好用工具 https://csacademy.com/app/graph_editor/ ---- <img src="https://live.staticflickr.com/65535/51873707080_94ef96f520_o.png" width="681" height="681" alt="Binary Tree"> ---- <img src="https://live.staticflickr.com/65535/51873070581_70a37c7fd0_o.png" width="681" height="681" alt="CommonGraph"> --- 所以這就是圖，不過這樣的東西到底會問怎樣的問題呢？ --- ## 例題一 ---- 輸入一個有向圖 G 與一個起點 s - 請計算由 s 出發可以到達的點數(不包含 s) - 並且計算這些可以到達的點與 s 的距離和 - 假設每個邊的長度均為 1。 - 兩點之間可能有多個邊 - 邊的起點與終點未必不同 ---- ### 例圖 ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"->{"2" "3"} "1"->{"2" "4","0"} "2"->"3" "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- ### 那怎麼辦 --- ## 存圖 ---- ### 鄰接串列(Adjacency Link) ---- 因為比賽中多數都用不到鄰接矩陣(Adjacency Matrix)，所以我先講鄰接串列 ---- 簡單說就是用 `vector` 陣列存 ```cpp= const int N=100010; vector<int> g[N]; ``` ---- `g[1]` 是一個 `vector` ，裡面存的是從 1 這個點出發可以到達的點 ---- 新增從 a 到 b 的邊 - 有向圖 `g[a].push_back(b);` - 無向圖還要加上 `g[b].push_back(a);` 因為無向圖代表的是 a 可以到 b ， b 也可以到 a 。 --- ## BFS(廣度優先搜索) ---- 依照這個順序訪問點 ---- ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"->{"2" "3"} "1"[color=red] "1"->{"2" "4","0"} "2"->"3" "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"[color=red] "0"->{"2" "3"} "1"[color=black] "1"->{"2" "4","0"} "2"->"3" "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"[color=black] "0"->{"2" "3"} "1"[color=black] "1"->{"2" "4","0"} "4"[color=red] "2"->"3" "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"[color=black] "0"->{"2" "3"} "1"[color=black] "1"->{"2" "4","0"} "4"[color=black] "2"[color=red] "2"->"3" "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"[color=black] "0"->{"2" "3"} "1"[color=black] "1"->{"2" "4","0"} "4"[color=black] "2"[color=black] "2"->"3" "3"[color=red] "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"[color=black] "0"->{"2" "3"} "1"[color=black] "1"->{"2" "4","0"} "4"[color=black] "2"[color=black] "2"->"3" "3"[color=black] "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- 以程式來實作的話需要一些簡單的資料結構(queue) ---- code ```cpp= vector<int> g[N]; void BFS(int s){ queue<int> q; q.push(s); while(!q.empty()){ int now=q.front(); q.pop(); for(auto e:g[now]){ q.push(e); } } } ``` ---- 不過光是這樣寫詪本沒用，我們需要在這樣的架構下添加一些東西 ---- ```cpp= struct info{ int to,dis; }; vector<int> g[N]; int bfs(int s){ queue<info> q; q.push({s,0}); int ret=0; while(!q.empty()){ info now=q.front(); q.pop(); ret+=now.dis; for(auto e:g[now.to]){ q.push({e,now.dis+1}); } } return ret; } ``` ---- ### 可是 ---- 如果是這樣的圖呢？ ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"->{"2"} "1"->{"0"} "2"->"1" {rank=same;"1" "2"} // Put them on the same level } ``` ---- 從 1 開始 - 將 2 推入 queue - 進入節點 2 - 將 3 推入 queue 中 - 進入節點 3 - 將 1 推入 queue 中 - ... ---- 好像變成無窮迴圈了 ---- 加入狀態 isv - true 此節點已被丟進 queue 過 - false 於上面相反 ---- code ```cpp= struct info{ int to,dis; }; vector<int> g[N]; bool isv[N]; int bfs(int s){ queue<info> q; q.push({s,0}); int ret=0; while(!q.empty()){ info now=q.front(); q.pop(); ret+=now.dis; for(auto e:g[now.to]){ if(!isv[e]){ isv[e]=true; q.push({e,now.dis+1}); } } } return ret; } ``` --- ## DFS(深度優先搜索) ---- 依照以下順序訪問節點 ---- ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"->{"2" "3"} "1"[color=red] "1"->{"2" "4","0"} "2"->"3" "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"[color=red] "0"->{"2" "3"} "1"[color=black] "1"->{"2" "4","0"} "2"->"3" "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"[color=black] "0"->{"2" "3"} "1"[color=black] "1"->{"2" "4","0"} "3"[color=red] "2"->"3" "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"[color=black] "0"->{"2" "3"} "1"[color=black] "1"->{"2" "4","0"} "3"[color=black] "2"[color=red] "2"->"3" "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"[color=black] "0"->{"2" "3"} "1"[color=black] "1"->{"2" "4","0"} "3"[color=black] "2"[color=black] "2"->"3" "4"[color=red] "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node[color=Blue,fontname=Courier,shape=circle] //All nodes will this shape and colour edge [color=Black, style=dashed] //All the lines look like this "0"[color=black] "0"->{"2" "3"} "1"[color=black] "1"->{"2" "4","0"} "4"[color=black] "2"[color=black] "2"->"3" "3"[color=black] "4"->{"3","2"} {rank=same;"1" "2" "3"} // Put them on the same level } ``` ---- DFS 的好處是可以用遞迴實作，而不用使用資料結構(也可以用 stack) ---- ```cpp= vector<int> g[N]; bool isv[N]; void DFS(int n){ for(auto u:g[n]){ if(!isv[u]){ isv[u]=true; DFS(u); } } } ``` ---- 因為 DFS 明顯比較好寫，因此在可以用 DFS 的情況下幾乎會使用他。 --- ## 例題二(ap325 P-7-2) ---- 題目是無向圖 ---- 補充說明：通常題目給的圖不一定可以從起點到達所有的點，這樣我們會說這個圖是非連通的，反之從起點可以到任何地方的稱為連通圖 ---- code ```cpp= #include<bits/stdc++.h> using namespace std; const int N=100010; int val[N]; vector<int> g[N]; bool isv[N]; int dfs(int n){ int ret=val[n]; for(int next:g[n]){ if(!isv[next]){ isv[next]=true; ret+=dfs(next); } } return ret; } void solve(){ int n,m; cin>>n>>m; for(int i=0;i<n;++i){ cin>>val[i]; } for(int i=0;i<m;++i){ int a,b; cin>>a>>b; g[a].emplace_back(b); g[b].emplace_back(a); } int ans=0; for(int i=0;i<n;++i){ if(!isv[i]){ isv[i]=true; ans=max(ans,dfs(i)); } } cout<<ans<<"\n"; } int main(){ ios::sync_with_stdio(0);cin.tie(0); solve(); } ``` --- ## 常見題型 ---- ### 格子圖 - [CSES_graph_1](https://cses.fi/problemset/task/1192) - [CSES_graph_2](https://cses.fi/problemset/task/1193) ---- 先來看第一題 - 給你一張圖，請你算出房間數量。地圖有 $n \times m$ 個格子，每一個格子不是地板就是牆壁。你可以往上下左右的地板行走，所有依照這個方式走的到的位置都算同一個房間。 - 第一行輸入兩個數字 $n,m$ ，緊接著是 $n$ 行 $m$ 列的字元(字串)，`'#'` 表示牆壁，`'.'` 表示地板。 ---- ---- 第二題 - 給你一張圖，請你從 A 走到 B。地圖有 $n \times m$ 個格子，每一個格子不是地板就是牆壁。你可以往上下左右的地板行走，所有依照這個方式走的到的位置都算同一個房間。 - 第一行輸入兩個數字 $n,m$ ，緊接著是 $n$ 行 $m$ 列的字元(字串)，`'#'` 表示牆壁，`'.'` 表示地板， A 是起點， B 是終點。 ---- 第二題自行練習參考程式碼 ```cpp= #include<bits/stdc++.h> #pragma GCC optimize ("O3,unroll-loops,fast-math") using namespace std; // 3 // 2 0 // 1 const int dx[4]{1,0,-1,0},dy[4]{0,-1,0,1}; map<int,char> toc{{0,'R'},{1,'U'},{2,'L'},{3,'D'}}; map<char,int> toi{{'R',0},{'U',1},{'L',2},{'D',3}}; struct info{ int r,c; info(int _r,int _c){ r=_r; c=_c; } }; int n,m; vector<string> mp,tp,pre; string ans; info bfs(int r,int c){ queue<info> q; q.emplace(r,c); while(!q.empty()){ info now=q.front(); q.pop(); if(tp[now.r][now.c]=='B'){ return info(now.r,now.c); } for(int i=0;i<4;i++){ int px=now.c+dx[i],py=now.r+dy[i]; if(px>=0 && py>=0 && px<m && py<n){ if(mp[py][px]!='#'){ mp[py][px]='#'; pre[py][px]=toc[i]; q.emplace(py,px); } } } } return info(-1,-1); } void solve(){ mp.clear(); cin>>n>>m; for(int i=0;i<n;i++){ string line; cin>>line; mp.emplace_back(line); } tp=pre=mp; info pos(-1,-1),st(0,0); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(mp[i][j]=='A'){ pos=bfs(i,j); st=info(i,j); break; } } } if(pos.r!=-1){ cout<<"YES"<<"\n"; while(pos.r!=st.r || pos.c!=st.c){ ans+=pre[pos.r][pos.c]; int p=toi[pre[pos.r][pos.c]]; pos.r-=dy[p]; pos.c-=dx[p]; } reverse(ans.begin(),ans.end()); cout<<ans.size()<<"\n"<<ans<<"\n"; }else{ cout<<"NO"<<"\n"; } } int main(){ ios::sync_with_stdio(0);cin.tie(0); // freopen("test_input.txt","r",stdin); // freopen("output.txt","w",stdout); int t=1; while(t--){ solve(); } } ``` ---- ### 一般圖 - [CSES_graph_3](https://cses.fi/problemset/task/1666/) - [CSES_graph_4](https://cses.fi/problemset/task/1667/) ---- - 給你 $n$ 個點 $m$ 條無向邊。請你找出要讓這張圖連通的最少所需新增邊數。還有給出具體方案。節點編號為 $1...n$ - 第一行輸入兩個數字 $n,m$ ，接下來有 $m$ 行，輸入邊a,b - 保證沒有自環或重邊 ---- ---- 第二題 - 給你 $n$ 台電腦 $m$ 組連接關係。請你找出從點 $1$ 能否到點 $n$ 。如果可以，一並輸出最短路徑。 - 第一行輸入兩個數字 $n,m$ ，接下來有 $m$ 行， - 保證沒有自環或重邊 ---- 第二題自行練習參考程式碼 ```cpp= #include<bits/stdc++.h> using namespace std; const int N=100010; int n,m,a,b; int pre[N]; vector<int> g[N]; bool isv[N]; int bfs(int u,int v){ queue<int> q; q.emplace(u); while(!q.empty()){ int now=q.front(); q.pop(); if(now==v){ return v; } for(auto i:g[now]) if(!isv[i]){ isv[i]=true; pre[i]=now; q.emplace(i); } } return -1; } void solve(){ cin>>n>>m; for(int i=1;i<=m;++i){ int a,b; cin>>a>>b; g[a].emplace_back(b); g[b].emplace_back(a); } a=1,b=n; pre[a]=a; isv[a]=true; int p=bfs(a,b); if(p!=-1){ vector<int> ans; while(p!=a){ ans.emplace_back(p); p=pre[p]; } ans.emplace_back(a); cout<<ans.size()<<"\n"; reverse(ans.begin(),ans.end()); for(int i=0;i<ans.size();++i){ cout<<ans[i]<<" "; } }else{ cout<<"IMPOSSIBLE"<<"\n"; } } int main(){ ios::sync_with_stdio(0);cin.tie(0); int t=1; while(t--){ solve(); } } ``` --- ## 圖論演算法 ---- ### 目錄 - 二分圖(Bipartite graph) - 最短路(Shortest Path) - 全點對 - 單點源 - 最小生成樹(Minimum Spanning Tree) - DAG(Directed Acyclic Graph) - 拓鋪排序(Topological Sorting) --- ## 二分圖 ---- 有沒有一種方式可以將圖中的點分成兩組，使組內沒有成員之間的邊。 ---- 如下圖 <img src="https://live.staticflickr.com/65535/51943863462_0d65d866f1_n.jpg" width="299" height="299" alt="二分圖"> ---- ### 二分圖判定 ---- 想像將圖上色，用 12 表示 ---- code ```cpp= int color[N]; bool isBipartiteGraph(int n){ for(auto u:g[n]){ // 用 color==0 代替 bool isv[N]; if(color[u]==0){ color[u]=color[n]%2+1; if(!isBipartiteGraph(u)) return false; }else if(color[u]==color[n]){ return false; } } return true; } ``` ---- - [CSES_graph_5]https://cses.fi/problemset/task/1668 ---- - 有 n 個人， m 個朋友關係，請你將他們分兩組，使得各組內成員間皆沒有朋友關係 - 第一行輸入 n, m ，接下來有 m 行，每行有兩個數字 a, b ，表示 a 與 b 之間有朋友關係， n 個人編號 1~n - 保證沒有自己與自己是朋友的，且相同朋友關係不會建立兩次 - 輸出 n 個數字，每一個都是 1 或 2 ，第 k 個數字表示第 k 個人的組別，可以輸出任何一種合法的解 - 無解時輸出 "IMPOSSIBLE" (不含括號). --- ## 最短路徑 ---- 這邊我們要先進入另一個章節「動態規劃」 ---- ### 全點對 ### Floyd-Warshall ---- - `dp[i][j][k]` 表示經過前 k 個點"鬆弛"後從 i 到 j 的最短距離 - 經過一系列的通靈後，我們可以得知下式 - `dp[i][j][k] = min(dp[i][j][k-1],dp[i][k][k-1]+dp[k][j][k-1]);` - 由於 `dp` 過程中只會用到 `dp[i][j][k-1]` ，所以第三個可以省略 - 最後就像下式 - `dp[i][j] = `</br>`min(dp[i][j],dp[i][k]+dp[k][j])` ---- code ```cpp= for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]); } } } // 也可以透過巨集簡化 #define REP(i,s,n) for(int i=(s);i<=(n);++i) REP(k,1,n) REP(i,1,n) REP(j,1,n){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]); } ``` ---- ### 單點源 ---- ### 1.Bellman-Ford ---- 如果只要求一個起點，所有到起點 s 的最短距離又不可以依據三角不等式決定距離時(BFS不適用) ---- 如下圖 <img src="https://live.staticflickr.com/65535/51972600276_091292c8a5_o.png" width="324" height="324" alt="不符和三角不等式的圖"> ---- 很明顯從 2 繞到 1 拜訪 4 比較快，更何況有邊權是負的情況 ---- - 所以，同樣經過精湛的通靈，我們發明一個新名詞"鬆弛" - 顧名思義，鬆弛就是在不滿足三角不等式的區域做的 - 具體請講師說明(阿就是我 :rolling_on_the_floor_laughing:) ---- ---- 在實作上，我們不再使用 `vector<int> g[N];` 來存圖，轉而使用 `struct` 所以順便複習一下 ```cpp= struct edge{ int from,to,dis; // 建構式 edge(int f=0,int t=0,int d=0){ from=f; to=t; dis=d; } }; vector<edge> es; int main(){ int n; cin>>n; for(int i=0;i<n;++i){ int f,t,d; cin>>f>>t>>d; // 剛剛的建構式單純是為了這樣方便 es.emplace_back(f,t,d); } } ``` ---- ```cpp= const int INF=0x3f3f3f3f; int dis[N]; void Bellman_Ford(int s){ fill(dis,dis+N,INF); dis[s]=0; while(true){ bool update=false; for(auto e:es){ if(dis[e.from]!=INF && dis[e.from]+e.dis<dis[e.to]){ update=true; dis[e.to]=dis[e.from]+e.dis; } } if(!update){ break; } } } ``` ---- 跑完之後 `dis` 陣列裡面存的就會是從起點 s 到 --- ## 進階內容 ---- ### 目錄 - DFS Tree - 網路流(Flows) - 雙連通分量 ---- 很多講師也不會，提供關鍵字讓大家搜尋

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.