圖論基礎

圖論在演算法這門學科裡佔了十分重要的地位，他可以用來表示許多種問題的結構，也可以從中發現不同的演算法和性質。

相信大家其實跟圖論的「圖」不陌生，像是心智圖，或是各種不同的地圖等等，都可以被表示成圖，因此也可以用圖論的方式來思考相關的問題，像是兩個點之間的最短距離等。

讓我們直接來看一張「圖」的例子：

這就是一張圖 (Graph)，一個圖 $G$ 是一些頂點 (Vertices, Nodes) 和邊 (Edges) 的集合，常用 $G(V, E)$ 表示。頂點是圖中的圓圈 $v_0, v_1, \dots$、邊則是連接兩個點的線，寫作 $(v_0, v_1), (v_2, v_3)$ 等。頂點的集合通常寫為 $V$，邊的集合通常寫為 $E$，因此這張圖可以寫為 $G(V, E)$，而點數和邊數可以分別用 $|V|, |E|$ 表示。

如果兩個點之間有一條邊連通，那麼我們會說他們是相鄰的或是鄰接的 (adjacent)，像是 $v_1, v_3$ 相鄰，$v_0, v_4$ 不相鄰。如果有一系列的點兩兩相鄰（像是 $v_0, v_1, v_3, v_2$）那麼他們就是一條路徑，而路徑的長度就是中間有幾條邊。如果兩個點之間存在一條路徑，那麼這兩個點就是連通的。

另外，有一種圖的邊是有方向的，稱為有向圖 (Directed Graph)。如下：

在這種圖裡面，路徑就必須沿著箭頭走。

除此之外，圖論裡還有很多很多名詞，以下整理一些常見的名詞：

1. 圖 (Graph)：許多頂點與邊的集合，常用 $G(V, E)$ 表示。

2. 頂點 (Vertex)：就是頂點 。常用 $v$ 表示。$V$ 就是頂點的集合。

3. 邊 (Edge)：連接兩個頂點的東西，可表示成 $e = (u, v)$。$E$ 就是邊的集合。

4. 有向/無向 (Directed/Undirected) 邊：如果 $(u, v)$ 與 $(v, u)$ 代表的是同一條邊，則稱這條邊是無向邊，反之則其中任一條邊為有向邊。

5. 度數 (Degree)：一個頂點連接的邊數，即為這個頂點的度數。

6. 入度/出度 (Indegree/Outdegree)：若為有向邊，則度數分為入度與出度，分別代表以此頂點為終點與起點的邊數。

7. 鄰接 (Adjacent)：如果兩個頂點間有邊連接，則稱這兩個頂點鄰接，也可以稱為相鄰。

8. 自環 (Self Loop)：連接相同頂點的邊，即 $(v, v)$。

9. 重邊 (Multiple Edge)：兩條或以上連接相同兩個點的邊。

10. 路徑 (Path)：一個頂點與邊交錯的序列，滿足每個邊都要連接兩個頂點，且從頂點開始、頂點結束。以 $(v_s, e_1, v_1, e_2, v_2, ..., v_e)$ 表示。

11. 簡單路徑 (Simple Path)：不包含重複頂點的路徑。

12. 迴路 (Circuit)：起點與終點為相同頂點的路徑。

13. 環 (Cycle)：只有起點與終點為相同頂點的路徑。

另外，圖也可以根據一些性質進行分類。

1. 有向圖/無向圖：每條邊都是無向邊的圖稱為無向圖，反之為有向圖。

2. 帶權圖/不帶權圖：有時點上或邊上會有權重，稱為帶權圖。

3. 連通圖：把所有邊變成無向邊後，對於圖上的所有頂點對 $(u, v)$，都存在一個起點為 $u$，終點為 $v$ 的路徑，則稱這個圖為連通圖。

4. 強連通圖：若有向圖上的所有頂點對 $(u, v)$，都存在一個起點為 $u$，終點為 $v$ 的路徑，則稱這個圖為強連通圖。

5. 簡單圖：沒有重邊以及自環的圖，不一定連通。

6. 完全圖：每個頂點都與圖上其他所有頂點鄰接的圖，稱為完全圖。

7. 子圖：今有兩圖 $G(V, E)$ 與 $H$，若對於所有屬於 $H$ 的頂點 $v_i$ 與邊 $e_i$ 皆有 $v_i \in V$ 且 $e_i \in E$（即 $H$ 內所有頂點與邊都屬於 $G$），則稱 $H$ 是 $G$ 的子圖。

8. 補圖：若圖 $G$ 與圖 $H$ 的頂點集合相同，且兩圖的邊集合聯集為完全圖、交集為空集合，則稱圖 $G$ 與圖 $H$ 互為補圖。

9. 樹：沒有環的連通無向圖稱為樹。

10. 森林：很多樹（包括一棵）的聯集稱為森林。

11. 二分圖：如果可以將一張圖的點集分為兩部分，同一部分的任兩點不鄰接，則稱為二分圖。

12. 有向無環圖：簡稱 DAG，就是沒有環的有向圖。

13. 稀疏圖/稠密圖：如果邊數十分多（如完全圖），也就是$|E| = O(|V^2|)$，則稱這個圖是稠密圖。若邊數不多（$|E| = O(|V|)$ 或 $|E| = O(|V|\log|V|)$），則稱為稀疏圖。

在學習圖論的時候，會學到各式各樣的演算法，一定要先確定要用什麼方式把圖存下來會比較好處理。這裡提供了三種把圖存在記憶體裡的方式，各自有優缺利弊，在不同圖論算法上有不同應用。

通常測資在輸入一張圖時，會先給定兩個數 $n, m$，分別代表頂點數以及邊數，接下來會有 $m$ 行，每行輸入兩個數字 $u_i, v_i$，代表有一條邊從頂點 $u_i$ 連至頂點 $v_i$，如果是帶權圖，那麼每行會輸入三個數，分別代表兩端點以及權重。讓我們把這種輸入格式轉成方便處理的形式吧！

鄰接矩陣是把圖存下來最直覺的想法。考慮一張無向圖：

我們可以將這張圖轉成以下二維陣列（矩陣）$A$：
$$\begin{bmatrix}
0 & 1 & 0 & 0 & 0\\
1 & 0 & 1 & 1 & 1\\
0 & 1 & 0 & 1 & 1\\
0 & 1 & 1 & 0 & 1\\
0 & 1 & 1 & 1 & 0
\end{bmatrix}$$

儲存的方法是，若頂點 $i$ 與頂點 $j$ 之間有邊時，就令 $A[i][j] = A[j][i] = 1$，否則 $A[i][j] = 0$。

int A[MAX_N][MAX_N]; // 初始化為 0
int main(){
    int n, m, a, b;
    cin >> n >> m;
    for(int i = 0 ; i < m; i++){
        cin >> a >> b;
        A[a][b] = A[b][a] = 1; // 有邊則改為 1
    }
}

鄰接矩陣可以在 $O(1)$ 時間檢查兩個頂點之間是否有邊，在一些特定演算法如 Floyd Warshall 等也會有比較好的實作優勢，但它有一個致命的缺點，就是需要用到 $O(|V|^2)$ 的記憶體。而在程式競賽中，圖論的題目其實時常會出到 $|V| = 10^5$ 這種量級，當然，在這種情況下題目的 $|E|$ 自然不會太大，可是使用鄰接矩陣就會直接無法存下整張圖，因此在這種情況下我們得換另一種方式存圖。

對於稀疏圖，用鄰接串列來儲存是一個比較好的選擇。用同一張圖來舉例，可以將它轉換成下列鄰接串列：

$$\begin{matrix}
0: & 1\\
1: & 0 & 2 & 3 & 4\\
2: & 1 & 4 & 3\\
3: & 1 & 4 & 2\\
4: & 2 & 3 & 1\\
\end{matrix}$$
每個數字 $i$ 後面接的一長串數字就是頂點 $i$ 有連接到的所有頂點的編號。注意串列串的一串數字是無序的，所以檢查兩個點是否有鄰接的最差時間複雜度是 $O(|E|)$。

我們常用一個 vector<int> G[MAX_N] 來實作鄰接串列。 G[i] 是一個 vector，這裡儲存所有與頂點 $i$ 鄰接的所有頂點的編號，如果是帶權圖，就能儲存一個 pair，表示鄰接頂點的編號與這條邊的權重。以下是將輸入轉成鄰接串列的方法。

vector<int> G[MAX_N];
int main(){
    int n, m, a, b;
    cin >> n >> m;
    for(int i = 0 ; i < m; i++){
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a); // 如果是無向圖必須加上反向邊
    }
}

鄰接串列應該是演算法競賽裡最常出現的圖儲存方式了，超過半數的問題都是用鄰接串列實現。接下來要提到的 DFS、BFS、最短路徑、二分圖塗色問題等等，都可以用鄰接串列來完成。

這個東西的英文叫 Edge List，就是一堆邊的集合，這個儲存方式比較簡單也比較接近輸入格式，就是用個
vector 將所有邊的兩端點儲存下來，維持原本的輸入格式也可以應用在一些好用的演算法。以下是範例程式碼。

vector<pair<int,int>> E;
int main(){
    int n, m, a, b;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        E.push_back({a, b});
    }
}

這種儲存方式可以解決最小生成樹的問題，或者實作一些只需要枚舉邊的演算法。

有了圖之後，我們就到各個頂點看看吧！Let's go！

我們可以把 DFS 想像成以下的樣子：想像有一個探險家從某一個點出發，在經過每一個點的路上插一個旗子，持續的往還沒看過的點走。如果在某個位置，不存在任何還沒看過的點，他就會往回走一個點，並且繼續看下去。

以下的程式描述了 DFS 的過程：

vector<int> G[MAX_N];
bool visited[MAX_N] = {};
void dfs(int s){
    // process vertex s
    visited[s] = true;
    for(auto t : G[s]){
        if(!visited[t]) dfs(t);
    }
    return;
}

可以想像「執行中的函式」是探險者，$s$ 是目前所在的點，而 return 則是往回走的過程。

值得注意的是：一次 DFS 只能拜訪過與起點連通的所有節點，如果你想遍歷整張圖的所有節點，必須對所有未被拜訪過的頂點進行 DFS，才能確保所有節點都被計算到。這樣雖然可能會進行 $O(|V|)$ 次 DFS，但是 visited 陣列每格最多只會被改成 true 一次，所以總複雜度仍然是 $O(|V|)$。

int main(){
    // 在這裡輸入鄰接串列
    for(int i = 0; i < n; i++){
        if(!visited[i]) dfs(i); // 拜訪所有節點
    }
}

相較於深度優先搜尋一路衝到底的精神，廣度優先搜尋比較接近一層一層的探索。可以參考以下的程式：

vector<int> G[MAX_N];
bool visited[MAX_N] = {};
queue<int> que;
void bfs(int s){
    que.push(s);
    while(!que.empty()){
        int v = que.front(), que.pop();
        // process vertex v
        visited[v] = 1;
        for(auto t : G[v]){
            if(!visited[t]) {
                visited[t] = 1; //這個很重要！
                que.push(t);
            }
        }
    }
}

queue 裡面的元素代表的是「有被別的點看到，但是還沒從那個點開始走」的點。BFS 一樣可以對整張圖進行遍歷，不過 BFS 有一個性質，就是先被處理到的點與起點的距離會比較近，也就是說這種演算法可以計算出起點到圖上任一點的「最短路徑」長度。讓我們看看以下例題：

對於這個問題，可以記錄一個陣列 dist[i] 代表從起點到頂點 $i$ 的最短路徑，顯然，起點到起點的最短距離是 $0$。然後從起點開始 BFS，每次抵達一個節點 $v$ 時，就將自己附近沒被標記過的節點設成 dist[v]+1，直到整個圖都被計算過之後，再存取終點的 dist 值即可。此外，因為 BFS 可以對整張圖進行遍歷，所以假設起點不動，一次 BFS 就可以算出起點到圖上任意終點的最短路徑。

int dist[MAX_N];
int visted[MAX_N];
vector<int> G[MAX_N];
queue<int> que;
void bfs(int s){
    dist[s] = 0;
    que.push(s);
    while(!que.empty()){
        int v = que.front(), que.pop();
        visited[v] = true;
        for(auto t : G[v]){
            if(!visited[t]){
                dist[t] = dist[v] + 1;
                que.push(t);
            }
        }
    }
}

以下用一些例題來舉例說明完全搜尋的用處吧！

這題是個暖身題，十分容易。就是從頂點 $A$ 開始 DFS，最後檢查 visited[B] 是否為真就行了，輕輕鬆鬆。

這題一樣是 DFS 的應用。我們可以把照片想像成圖，在周圍八格的字元想像成鄰接。DFS 一次可以把一整個連通塊的地方都搜尋過一遍，所以我們可以掃過所有點，如果遇到綠地或空地就從那裡開始 DFS，每次 DFS 都將整個連通塊的綠地或空地破壞掉（改成）其他標記，再將答案加上 $1$。這樣枚舉完所有點後，計算完的答案就是正確的連通塊數量了！

#include <bits/stdc++.h>
using namespace std;
char city[110][110];
int w, h, greenland = 0, emptyspace = 0;
void dfs(int x, int y, char ch){
    city[x][y] = 'V'; // visited
    int dx[] = {1,  1,  1,  0, -1, -1, -1,  0};
    int dy[] = {1,  0, -1, -1, -1,  0,  1,  1};
    for(int i = 0; i < 8; i++){
        if(x+dx[i] >= w || x+dx[i] < 0) continue;
        if(y+dy[i] >= h || y+dy[i] < 0) continue;
        if(city[x+dx[i]][y+dy[i]] == ch){
            dfs(x+dx[i], y+dy[i], ch);
        }
    }
}
int main(){
    cin >> h >> w;
    for(int i = 0; i < w; i++){
        for(int j = 0; j < h; j++)
            cin >> city[i][j];
    }
    for(int i = 0; i < w; i++){
        for(int j = 0; j < h; j++){
            if(city[i][j] == '-')
                dfs(i, j, '-'), emptyspace++;
            if(city[i][j] == 'G')
                dfs(i, j, 'G'), greenland++;
        }
    }
    cout << greenland << ' ' << emptyspace << endl;
}

這題是一個麻煩題，不只是要找到最短路徑長，還要把整個最短路徑輸出。最短路徑問題的處理大家都已經不陌生了，一樣是用一個三維陣列 dist[][][] 儲存著從起點到那個點的最短路徑長。因為最後要將整條路徑輸出，所以除了記錄最短路徑長之外，還要順便記錄前一步是從哪裡來。轉移來源的儲存方式有很多種，可以記錄走來的方位（上下左右等等），也可以直接紀錄座標，兩種方式都能達到一樣的效果。有了轉移來源之後，就可以從終點沿路走回去，最後再倒轉輸出即可。

#include<bits/stdc++.h>
using namespace std;

int G[51][51][51];
int dist[51][51][51];
int pre[51][51][51];

// 六種轉移方式
int dx[] = {-1, 1, 0, 0, 0, 0};
int dy[] = { 0, 0,-1, 1, 0, 0};
int dz[] = { 0, 0, 0, 0,-1, 1};

struct point{ // 儲存點坐標
    int x, y, z;
    point(int x, int y, int z): x(x), y(y), z(z){}
};

int main(){
    // input
    int x, y, z;
    cin >> z >> y >> x;
    for(int i = 0; i < x; i++){
        for(int j = 0; j < y; j++){
            for(int k = 0; k < z; k++)
                cin >> G[i][j][k];
        }
    }
    // BFS
    queue<point> que;
    que.push(point(0, 0, 0));
    dist[0][0][0] = 1;
    while(!que.empty()){
        point now = que.front();
        que.pop();
        for(int i = 0; i < 6; i++){
            point nxt(now.x+dx[i], now.y+dy[i], now.z+dz[i]);
            if(nxt.x >= x || nxt.x < 0) continue; // 超出邊界
            if(nxt.y >= y || nxt.y < 0) continue;
            if(nxt.z >= z || nxt.z < 0) continue;
            if(dist[nxt.x][nxt.y][nxt.z] != 0) continue; // visited
            if(G[nxt.x][nxt.y][nxt.z] == 0){
                dist[nxt.x][nxt.y][nxt.z] = dist[now.x][now.y][now.z] + 1;
                pre[nxt.x][nxt.y][nxt.z] = i; // 紀錄轉移來源是第 i 種
                que.push(nxt);
            }
        }
    }
    // back tracking
    if(dist[x-1][y-1][z-1] == 0 || G[0][0][0] == 1){
        // 注意 no route 的條件，容易漏判
        cout << "no route" << endl;
        return 0;
    }
    stack<point> ans; // 反向輸出，用 stack
    x--, y--, z--; // 從終點 (x-1,y-1,z-1) 開始走
    while(x || y || z){ // 直到走回起點 (0,0,0)
        ans.push(point(x, y, z));
        int i = pre[x][y][z];
        x -= dx[i], y -= dy[i], z -= dz[i];
    }
    // output
    cout << "(1,1,1)";
    while(!ans.empty()){
        point now = ans.top();
        cout << "->(" << now.z+1 << ',' << now.y+1 << ',' << now.x+1 << ")";
        ans.pop();
    }
}

這是 BFS 的經典題。有了上一題處理方格的方法，相信這題一點都不難做。

這題要稍微想一下做法，有時候從起點 BFS 不是那麼有用。