---
# System prepended metadata

title: 單元八 圖論(Graph Theory)
tags: [C++]

---

# 單元八 圖論(Graph Theory)
圖論是一個極其重要的主題，因為許多問題可以被建構為圖和網絡的問題。理解並能夠實現圖論的各種演算法對於競技編程來說是非常關鍵的。具體應用比如： 路徑查找、樹和森林問題以及圖的遍歷。

---
## 名詞介紹
1. **圖 (Graph)**：是一種用來記錄關聯、關係的東西。
2. **點 (Vertex)**：圖中的一個**節點**。在圖的語境中，頂點用來表示一個實體或對象。
3. **邊 (Edge)**：連接兩個頂點的線，表示頂點之間的關系。

![graph1](https://hackmd.io/_uploads/S11lrbCzA.png)


## 有向圖
有向圖是一種邊具有方向性的圖。在有向圖中，邊從一個節點指向另一個節點。表示從一個節點到另一個節點有特定的指向。
![OIP](https://hackmd.io/_uploads/BkwlI-AGC.jpg)

## 有權圖與無權圖
圖上的點和邊可以有權重，邊的權重可能可以代表道路的長度，點可能可以代表都市的車輛數
左圖為無權圖，右圖為有權圖。
![Untitled](https://hackmd.io/_uploads/Hy_cgnJQC.png)

## 圖的表示
在C++中，圖通常可以用以下幾種方式表示：
* **相鄰矩陣**：使用二維資料結構，有關聯的點之間儲存為 $1$。
* **相鄰串列**：使用 list 或 vector，儲存起點與終點編號。

### 相鄰矩陣 (Adjacency Matrix)
範例：
![matrix](https://hackmd.io/_uploads/S1fIO-RfC.png)
程式碼：
```Cpp=
int graph[5][5];
```
```cpp=
void adjacency_matrix()
{
	for (int i=0; i<5; ++i)
		for (int j=0; j<5; ++j)
			graph[i][j] = 0; // 初始化為 0

	int a, b;	// 一條邊的端點、另一個端點
	while (cin >> a >> b)
		graph[a][b] = 1; // 1 表示有連結
}
```
將有關係的兩個節點以 $1$ 來表示
### 相鄰串列 (Adjacency List)
範例：
![螢幕擷取畫面 2024-05-12 231227](https://hackmd.io/_uploads/BkxFhIRMC.png)


程式碼：
```Cpp=
vector<int> list[5];
```
```cpp=
void adjacency_lists()
{
	for (int i=0; i<5; ++i)
		list[i].clear();

	int a, b;	// 一條邊的起點、終點
	while (cin >> a >> b)
		list[a].push_back(b);
}
```

## 圖的遍歷 (Graph Traversal)
圖的遍歷，也就是指通盤地讀取圖的資訊：決定好從哪裡開始讀，依照什麼順序讀，要讀到哪裡為止。
利用最簡單的資料結構 **queue** 和 **stack** ，就能製造不同的遍歷順序，得到兩種遍歷演算法：廣度優先搜尋 **BFS** 以及深度優先搜尋 **DFS**。
### BFS (Breadth-first Search) 
**廣度優先搜尋** (Breadth-first Search, BFS) 從一個源點開始，首先訪問所有與源點直接相連的節點，然後訪問與這些節點直接相連且尚未訪問過的節點，依此類推，直到遍歷完所有可達的節點。BFS 通常使用佇列來實現。
廣度優先利用佇列 (Queue) 的方式來處理。概念圖：
![20121027TnPd6lTzWS](https://hackmd.io/_uploads/HJH4VfRGC.jpg =80%x)
#### 用 BFS 實作最短路徑長：
![DB1FF9DC-63A1-41A7-836E-B27E5A24D11D](https://hackmd.io/_uploads/S1rEmMAM0.jpg =75%x)
請輸出 0 到各個節點的最短路徑長。
:::spoiler 程式碼：
```cpp=
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void bfsShortestPath(vector<vector<int>>& graph, int start) {
    int n = graph.size(); // 獲取圖中的節點數量
    vector<int> distances(n, -1); // 存儲從起點到每個點的最短路徑距離
    queue<int> q; // BFS 使用的佇列

    // 初始化
    distances[start] = 0; // 起始點到自己的距離是 0
    q.push(start); // 將起始點加入佇列

    while (!q.empty()) {
        int current = q.front(); // 取出佇列前面的元素
        q.pop();

        // 遍歷當前節點的所有鄰居
        for (int neighbor : graph[current]) {
            if (distances[neighbor] == -1) { // 如果這個鄰居沒有被訪問過
                distances[neighbor] = distances[current] + 1; // 設置距離
                q.push(neighbor); // 將這個鄰居加入佇列
            }
        }
    }

    // 輸出所有從起點到每個點的最短路徑長度
    for (int i = 0; i < n; ++i) {
        cout << "Shortest path from " << start << " to " << i << " is " << distances[i] << endl;
    }
}

int main() {
    // 範例圖的鄰接表表示
    vector<vector<int>> graph = {
        {1, 2},    // 鄰居 of vertex 0
        {0, 3},    // 鄰居 of vertex 1
        {0, 4},    // 鄰居 of vertex 2
        {1, 5},    // 鄰居 of vertex 3
        {2},       // 鄰居 of vertex 4
        {3}        // 鄰居 of vertex 5
    };

    bfsShortestPath(graph, 0); // 從節點 0 開始進行 BFS
    return 0;
}

```
:::
::: spoiler 輸出結果：
```
Shortest path from 0 to 0 is 0
Shortest path from 0 to 1 is 1
Shortest path from 0 to 2 is 1
Shortest path from 0 to 3 is 2
Shortest path from 0 to 4 is 2
Shortest path from 0 to 5 is 3
```
:::
### DFS (Depth-first Search)
**深度優先搜索** (Depth-First Search, DFS) 是一種用於遍歷或圖的算法。DFS 探索盡可能深的節點的分支，直到該節點無法再深入為止，然後回溯到先前的節點以探索其他分支。DFS 可以用遞歸方式實現，也可以使用顯式的堆堆疊來實現。
深度優先利用堆疊(Stack)的方式來處理。概念圖：
![201210276jKV7VdkNs](https://hackmd.io/_uploads/HkClrG0fA.jpg =80%x)
#### DFS 的遍歷
將展示如何對一個圖進行深度優先遍歷。提供遞迴實現和非遞迴（使用堆疊）實現兩種方式：
![DB1FF9DC-63A1-41A7-836E-B27E5A24D11D](https://hackmd.io/_uploads/HyYHzQCz0.jpg =75%x)
:::spoiler 遞迴寫法：
```cpp=
#include <iostream>
#include <vector>

using namespace std;

void dfsRecursive(vector<vector<int>>& graph, int node, vector<bool>& visited) {
    // 標記當前節點為已訪問
    visited[node] = true;
    cout << "Visited " << node << endl;

    // 遍歷所有鄰居
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {  // 如果鄰居未被訪問，則進行遞歸訪問
            dfsRecursive(graph, neighbor, visited);
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},    // 鄰居 of vertex 0
        {0, 3},    // 鄰居 of vertex 1
        {0, 4},    // 鄰居 of vertex 2
        {1, 5},    // 鄰居 of vertex 3
        {2},       // 鄰居 of vertex 4
        {3}        // 鄰居 of vertex 5
    };

    int startVertex = 0;
    vector<bool> visited(graph.size(), false);
    dfsRecursive(graph, startVertex, visited);

    return 0;
}

```
:::
:::spoiler 非遞迴寫法：
```cpp=
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfsStack(vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    stack<int> s;

    // 開始節點入堆疊
    s.push(start);

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        if (!visited[node]) {
            visited[node] = true;
            cout << "Visited " << node << endl;

            // 將所有未訪問的鄰居反向入堆疊，以符合給定的訪問順序
            for (int i = graph[node].size() - 1; i >= 0; i--) {
                int neighbor = graph[node][i];
                if (!visited[neighbor]) {
                    s.push(neighbor);
                }
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},    // 鄰居 of vertex 0
        {0, 3},    // 鄰居 of vertex 1
        {0, 4},    // 鄰居 of vertex 2
        {1, 5},    // 鄰居 of vertex 3
        {2},       // 鄰居 of vertex 4
        {3}        // 鄰居 of vertex 5
    };

    dfsStack(graph, 0);  // 從節點 0 開始進行 DFS

    return 0;
}

```
:::
:::spoiler 輸出結果：
```
Visited 0
Visited 1
Visited 3
Visited 5
Visited 2
Visited 4
```
:::
#### 範例一
* 用 DFS 實作迷宮問題：

![45FE0B4C-6D45-4774-AD98-416BD6AC0140](https://hackmd.io/_uploads/HJhpAM0MA.jpg =50%x)
請輸出 DFS 的所有遍歷路徑。
:::spoiler 程式碼：
```cpp=
#include <iostream>
#include <vector>
using namespace std;

// 定義移動的四個方向：上，下，左，右
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// 檢查當前位置是否有效
bool isValid(vector<vector<int>>& maze, int x, int y, vector<vector<bool>>& visited) {
    int n = maze.size(), m = maze[0].size();
    return x >= 0 && y >= 0 && x < n && y < m && maze[x][y] == 1 && !visited[x][y];
}

// DFS 函數
bool dfs(vector<vector<int>>& maze, vector<vector<bool>>& visited, int x, int y) {
    int n = maze.size(), m = maze[0].size();

    // 如果達到出口
    if (x == n-1 && y == m-1) {
        cout << "Path to exit: (" << x << ", " << y << ")\n";
        return true;
    }

    // 標記當前位置為已訪問
    visited[x][y] = true;
    cout << "Visiting: (" << x << ", " << y << ")\n";

    // 探索所有可能的方向
    for (auto dir : directions) {
        int newX = x + dir.first;
        int newY = y + dir.second;

        if (isValid(maze, newX, newY, visited)) {
            if (dfs(maze, visited, newX, newY)) {
                return true;
            }
        }
    }

    // 回溯前的處理
    return false;
}

int main() {
    vector<vector<int>> maze = {
        {1, 0, 1, 1, 1},
        {1, 1, 1, 0, 1},
        {0, 0, 0, 1, 1},
        {1, 1, 1, 1, 0},
        {1, 1, 1, 1, 1}
    };
    int n = maze.size(), m = maze[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    if (!dfs(maze, visited, 0, 0)) {
        cout << "No path found to exit.\n";
    }
    return 0;
}

```
:::
:::spoiler 輸出結果：
```
Visiting: (0, 0)
Visiting: (1, 0)
Visiting: (1, 1)
Visiting: (1, 2)
Visiting: (0, 2)
Visiting: (0, 3)
Visiting: (0, 4)
Visiting: (1, 4)
Visiting: (2, 4)
Visiting: (2, 3)
Visiting: (3, 3)
Visiting: (4, 3)
Visiting: (4, 2)
Visiting: (3, 2)
Visiting: (3, 1)
Visiting: (4, 1)
Visiting: (4, 0)
Visiting: (3, 0)
Path to exit: (4, 4)
```
:::
## 實戰演練
[a359: P-7-2. 開車蒐集寶物](https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a359)
Hint：使用DFS
:::spoiler 解答：
```cpp=
#include <bits/stdc++.h>
using namespace std;

int n, m; // n 是節點數量，m 是邊的數量
vector<int> arr[50005]; // 鄰接表，用來存儲圖
int treauser[50005]; // 存儲每個節點的寶藏值
bool visit[50005] = {false}; // 訪問標記，用於 DFS 過程中標記已訪問的節點

// DFS 函數，用於計算從節點 a 開始的所有連通節點的寶藏總和
int dfs(int a) {
    visit[a] = true; // 標記當前節點為已訪問
    int weight = 0; // 初始化當前節點的寶藏總和
    weight += treauser[a]; // 加上當前節點的寶藏值

    // 遍歷當前節點的所有鄰居
    for (int i = 0; i < arr[a].size(); i++) {
        if (visit[arr[a][i]] == false) { // 如果鄰居未被訪問，則進行 DFS
            weight += dfs(arr[a][i]);
        }
    }
    return weight; // 返回從當前節點出發的連通分量的寶藏總和
}

int main() {
    ios::sync_with_stdio(0); // 加快 C++ I/O
    cin.tie(0); // 解除 cin 和 cout 的綁定，進一步加速

    cin >> n >> m; // 讀入節點數和邊數
    for (int i = 0; i < n; i++) {
        cin >> treauser[i]; // 讀入每個節點的寶藏值
    }
    int temp1, temp2;
    for (int i = 0; i < m; i++) {
        cin >> temp1 >> temp2; // 讀入每條邊的兩個節點
        arr[temp1].push_back(temp2); // 無向圖，所以兩個方向都要添加
        arr[temp2].push_back(temp1);
    }
    int ans = 0; // 用於存儲最大的寶藏值
    for (int i = 0; i < n; i++) { // 遍歷所有節點
        if (visit[i] == false) { // 如果節點未被訪問，進行 DFS
            ans = max(ans, dfs(i)); // 更新最大寶藏值
        }
    }
    cout << ans; // 輸出最大的寶藏總和
    return 0;
}

```
:::
## 結語
通過本單元的學習，你應該已經對圖的基本概念、表示方式、以及基本的圖遍歷算法有了深入的理解。掌握了廣度優先搜索 BFS 和深度優先搜索 DFS 這兩種算法後，你將能夠解決如最短路徑、連通分量、迷宮探索等各種圖相關問題。
## 參考資料
iT邦幫忙
https://ithelp.ithome.com.tw/articles/10281404
Graph
https://web.ntnu.edu.tw/~algo/Graph.html
Medium-基礎演算法系列 
https://medium.com/%E6%8A%80%E8%A1%93%E7%AD%86%E8%A8%98/%E5%9F%BA%E7%A4%8E%E6%BC%94%E7%AE%97%E6%B3%95%E7%B3%BB%E5%88%97-graph-%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%88%87dijkstras-algorithm-6134f62c1fc2