# 圖論
---
## 目錄
- 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)
- 雙連通分量
----
很多講師也不會，提供關鍵字讓大家搜尋
{"metaMigratedFrom":"YAML","metaMigratedAt":"2023-06-16T19:21:27.761Z","title":"圖論","breaks":true,"contributors":"[{\"id\":\"3978a08d-c47c-4560-b04d-dfbd8e71d0a3\",\"add\":35011,\"del\":17401},{\"id\":\"4f67c477-a6ac-4743-a794-5e693b4248d6\",\"add\":28,\"del\":1}]"}