圖論

圖 \(G\) 由點 \(V\) 與邊 \(E\) 構成，記做 \(G=(V,E)\) 。
聽起來很難？

其實就是像這樣的東西

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
}

輸入一個有向圖 G 與一個起點 s

• 請計算由 s 出發可以到達的點數(不包含 s)
• 並且計算這些可以到達的點與 s 的距離和
• 假設每個邊的長度均為 1。
• 兩點之間可能有多個邊
• 邊的起點與終點未必不同

例圖

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 陣列存

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 。

依照這個順序訪問點

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
}

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
}

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
}

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
}

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
}

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

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);
        }
    }
}

不過光是這樣寫詪本沒用，我們需要在這樣的架構下添加一些東西

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;
}

可是

如果是這樣的圖呢？

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

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;
}

依照以下順序訪問節點

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
}

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
}

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
}

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
}

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
}

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)

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 的情況下幾乎會使用他。

題目是無向圖

補充說明：通常題目給的圖不一定可以從起點到達所有的點，這樣我們會說這個圖是非連通的，反之從起點可以到任何地方的稱為連通圖

code

#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
• CSES_graph_2

先來看第一題

• 給你一張圖，請你算出房間數量。地圖有 \(n \times m\) 個格子，每一個格子不是地板就是牆壁。你可以往上下左右的地板行走，所有依照這個方式走的到的位置都算同一個房間。
• 第一行輸入兩個數字 \(n,m\) ，緊接著是 \(n\) 行 \(m\) 列的字元(字串)，'#' 表示牆壁，'.' 表示地板。

第二題

• 給你一張圖，請你從 A 走到 B。地圖有 \(n \times m\) 個格子，每一個格子不是地板就是牆壁。你可以往上下左右的地板行走，所有依照這個方式走的到的位置都算同一個房間。
• 第一行輸入兩個數字 \(n,m\) ，緊接著是 \(n\) 行 \(m\) 列的字元(字串)，'#' 表示牆壁，'.' 表示地板， A 是起點， B 是終點。

第二題自行練習
參考程式碼

#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
• CSES_graph_4

• 給你 \(n\) 個點 \(m\) 條無向邊。請你找出要讓這張圖連通的最少所需新增邊數。還有給出具體方案。節點編號為 \(1...n\)
• 第一行輸入兩個數字 \(n,m\) ，接下來有 \(m\) 行，輸入邊a,b
• 保證沒有自環或重邊

第二題

• 給你 \(n\) 台電腦 \(m\) 組連接關係。請你找出從點 \(1\) 能否到點 \(n\) 。如果可以，一並輸出最短路徑。
• 第一行輸入兩個數字 \(n,m\) ，接下來有 \(m\) 行，
• 保證沒有自環或重邊

第二題自行練習
參考程式碼

#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)

有沒有一種方式可以將圖中的點分成兩組，使組內沒有成員之間的邊。

如下圖

二分圖判定

想像將圖上色，用 12 表示

code

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] =
min(dp[i][j],dp[i][k]+dp[k][j])

code

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不適用)

如下圖

很明顯從 2 繞到 1 拜訪 4 比較快，更何況有邊權是負的情況

• 所以，同樣經過精湛的通靈，我們發明一個新名詞"鬆弛"
• 顧名思義，鬆弛就是在不滿足三角不等式的區域做的
• 具體請講師說明(阿就是我 )

在實作上，我們不再使用 vector<int> g[N]; 來存圖，轉而使用 struct 所以順便複習一下

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);
    }
}

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)
• 雙連通分量

很多講師也不會，提供關鍵字讓大家搜尋