圖形 (graph)

電腦科學中的圖不是指我們常常看到的圖片喔 ! 在這裡，我們所指的圖是指由若干個點 (vertex) 跟邊 (edge) 所組成的圖形（下圖是一個範例）

這些圖形可以用來表示東西的不同關係。例如，在下圖一種關係就是把邊想成道路，每個點是一個城市，被連起來的點可以相互走到。

在圖論中，有一些在 APCS 會遇到的名詞需要先定義。

• 頂點 (vertex)：圖上面的點，可以用來代表事物
• 邊 (edge)：圖上面將點連起來的邊，可以用來代表兩個事務的特定關係
• 邊權 (weight)：邊上面的權重
• 度數 (degree)：一個點連到的邊的數量，如果是有向圖則可以再細分成入度 (指到他的邊數量）及出度（連出去的邊數量）
• 子圖（subgraph)：邊跟點都是原圖的邊跟點的子集合的圖，基本上就是原圖的一部分。
• 有向圖 (directed graph)：每個邊是有方向的（圖 1）
• 無向圖 (undirected graph)：每個邊沒有方向 （圖 1）
• 環 (cycle)：一條只有第一個和最後一個頂點重複的非空路徑 (圖 2)
• 連通圖 (connected graph)：代表圖上的任兩個點都可以透過一些邊走到對方（圖 3）
• 連通分量 (connected component)：連通的子圖

圖的走訪

在圖論中，我們常常會需要把整個圖走過一次。這邊我們介紹兩種最常見的走訪圖的方法：dfs (深度優先搜尋) 跟 bfs (廣度優先搜尋)！在儲存圖的時候，要注意是 0-based 還是 1-based 喔。

首先，有兩種存圖的方式 Adjacency List 跟 Adjacency Matrix。
Adjacency List 的概念是開很多個 vector 或是陣列，然後每個陣列裡面存的是編號所連到的點。例如點 1 如果有連到 2, 3 的話，編號 1 的 vector 裡面就會裝 2 3。這種用 List 的方式儲存點跟點之間連通的關係就叫做 Adjancecy List

const int mxn = 2e5 + 5; // 有幾個點
vector <int> G[mxn]; // 開很多個 vector

for(int i = 0;i < n;i++){
    int u, v;
    cin >> u >> v;
    G[u].push_back(v); // 點 u 可以走到點 v
    G[v].push_back(u); // 雙向圖的話就反著也設成連通
} 

第二種方式是 Adjacency Matrix。這種方式是開一個矩陣，也就是二維陣列紀錄點跟點 pair 連通的狀況。例如假如 1 可以連到 2。那在 matrix[1][2] 的地方就可以設成 1 代表有連通，其他地方都設成 0。這種方式在有些時候很好用，例如 Floyd Warshall。但是，在大多的情況下，這種方式要 O(n^2) 的空間，很容易太大，所以我們比較常使用 Adjacency List。

const int mxn = 2e5 + 5; // 有幾個點
int G[mxn][mxn];

for(int i = 0;i < n;i++){
    int u, v;
    cin >> u >> v;
    G[u][v] = 1;
    G[v][u] = 1; // 雙向圖的話就反著也設成連通
}

DFS 深度優先搜尋 (Depth-first search)

所謂 dfs 其實就跟走迷宮的方法很像。在走迷宮的時候，我們可能會朝著一條路走，直到走到不能在走為止，走不了的話就回到上一個岔路，往另一個岔路走走看。dfs 就是在模擬這種走法！dfs 可以用 stack 或是遞迴實現，這邊我就用遞迴的方式寫一次程式碼。而 dfs 的走訪順序就是下面那張取自 yale university 的圖片的紅色箭頭。每次就是朝著一個方向走到最底，不能走就返回到上一個岔路，繼續走。

這邊我們假設會先輸入兩個數字 n 代表有編號 1 ~ n 的點，m 代表有幾條邊，接著有 m 行，每行有點個數字，代表點 a 到點 b 有一條邊。

#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e5 + 5;
vector <int> G[mxn];
vector <bool> vis(mxn); // 記錄有沒有走過
void dfs(int u){
    if(vis[u]) return; // 有走過就不要再走了
    vis[u] = true; // 現在走過了
    for(int v : G[u]){
        dfs(v);
    }
}
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }
    dfs(1);
}

上面是一個非常簡易的 dfs 程式碼。在走訪圖的時候，如果給的圖有環的話就可能會造成無限迴圈，因為會一直繞圈圈。因此，我們需要多開一個 vis 陣列紀錄每個點有沒有走過，有走過的話就不用再走了。

而 dfs 算是一個很好寫的走訪方式，而他是很多更進階的演算法的基礎，他也可以有很多應用！例如：

• 判斷圖是不是連通 (看看是不是全部點的 vis 都設成走過了)
• 找環 (可能要改一下 vis，把 vis = 1 當作正在走，把 vis = 2 當作走完了)
• 類似這種題目

BFS 廣度優先搜尋 (Breadth First Search)

BFS 的想法是用階層的方式走，也就是每次走到一個點，都把他連到的下一個點加到一個 queue 裡面，這樣的話，我們就可以得知從一開始的節點到每個節點的最短距離。

BFS 可以讓我們得知從源節點到每個點的最短距離，因為我們是先走完全部距離 = 1，再走距離 = 2，再走到距離 = 3 … 每次遇到的時候一定就是最短的距離。以下的 code 是我用 queue 實作 bfs 並把 1 當作源節點，找到他跟每個點的最短距離。

#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e5 + 5;
vector <int> G[mxn];
vector <int> vis(mxn, -1); // 記錄距離，-1 代表沒走到過
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }
    queue <int> q;
    q.push(1);
    dis[1] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int v : G[u]) {
            if(dis[v] == -1) {
                q.push(v);
                dis[v] = dis[u] + 1; // 子節點的距離會是父節點 + 1 因為他們只隔一條邊
            }
        }
    }
}

因為我們是用 queue 的資料結構實作 bfs，先進去的會先出來，所以我們一定是照著距離 = 1，再走距離 = 2，再走到距離 = 3 … 重新走到一個節點就不用理他，因為他的距離一定只會更長而已

而 bfs 最大的好處就是他可以得知最短距離，在要找沒有邊權的最短路徑時非常好用! 例如這題

拓撲排序 (Topological Sort)

在有向無環圖 (Directed Acyclic Graph, 簡稱 DAG) 上，我們可以為點 “排序”，也就是為圖上的點排一個合法的順序。所謂合法的順序是指假如點A有一條邊指到點B，那點A的順序一定要在點B前面，而圖上的每條邊都要滿足這個條件。所以，一張圖的拓撲排序可能有很多種。在下面圖片中，除了 A, B, C, D, E, F 外，A, B, C, E, D, F 也是一種可能的拓撲排序。

所以，我們可以發現，為甚麼一定要是有向無環圖才能找到拓撲排序。如果圖有環的話，我們一定不能找到一種方式是連到他的人都要排在前面的方法。而這個排序有甚麼用呢? 這個演算法可以幫助我們在圖上找到一種合法的走訪方式。我們也可以用點跟邊表示一些順序，例如一定要上完課 A 才能上課 B。在圖上的動態規劃，我們常常會用到這種演算法為圖找到一種可以 DP 的順序。

我們找到這個排序的概念就是開一個陣列記錄目前進入排序的點。一個點要可以被放進排序，一定要沒有邊指到他。所以，當一個點沒有被任何點指到時，就可以把那個點放進排序，並把點拔掉，再把他連到的點的入度減一即可。

在實作上，我們可以利用陣列 in[] 來記錄每個點 in degree，也就是有多少條邊指到他。另外，我們用一個 queue 來記錄哪些點的 in degree 是 0，當如果是 0 的時候就可以放進排序，並把點拔掉。而如果有很多個點同時都沒有被邊指到，那要先放誰進去都可以，因為他們被放進去都是合法的。如果題目要求一些特別的順序，可以考慮用 priority_queue 輔助判斷。存圖的方式可以用上面提到的連接串列來儲存連通資訊。

#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e5 + 5;
vector <int> G[mxn]; // 儲存圖
vector <int> in(mxn); // 儲存入度
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        int u, v; 
        cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
        in[v] ++; // 點 v 的入度 + 1
    }
    queue <int> q;
    for(int i = 0;i < n;i++){
        if(in[i] == 0) q.push(i);
    }
    vector <int> ans;
    while(!q.empty()) {
        int u = q.top();
        q.pop();
        for(int v : G[u]) {
            in[v] --; // 把點 u 拔掉，所以點 v 入度 - 1
            if(in[v] == 0) q.push(v);
        }
        ans.push_back(u);  
    }
    for(int x : ans) cout << x << '\n';
}