# 單元八 圖論(Graph Theory)
圖論是一個極其重要的主題，因為許多問題可以被建構為圖和網絡的問題。理解並能夠實現圖論的各種演算法對於競技編程來說是非常關鍵的。具體應用比如： 路徑查找、樹和森林問題以及圖的遍歷。
---
## 名詞介紹
1. **圖 (Graph)**：是一種用來記錄關聯、關係的東西。
2. **點 (Vertex)**：圖中的一個**節點**。在圖的語境中，頂點用來表示一個實體或對象。
3. **邊 (Edge)**：連接兩個頂點的線，表示頂點之間的關系。
## 有向圖
有向圖是一種邊具有方向性的圖。在有向圖中，邊從一個節點指向另一個節點。表示從一個節點到另一個節點有特定的指向。
## 有權圖與無權圖
圖上的點和邊可以有權重，邊的權重可能可以代表道路的長度，點可能可以代表都市的車輛數
左圖為無權圖，右圖為有權圖。
## 圖的表示
在C++中，圖通常可以用以下幾種方式表示：
* **相鄰矩陣**：使用二維資料結構，有關聯的點之間儲存為 $1$。
* **相鄰串列**：使用 list 或 vector，儲存起點與終點編號。
### 相鄰矩陣 (Adjacency Matrix)
範例：
程式碼：
```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)
範例：
程式碼：
```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) 的方式來處理。概念圖：
#### 用 BFS 實作最短路徑長：
請輸出 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)的方式來處理。概念圖：
#### DFS 的遍歷
將展示如何對一個圖進行深度優先遍歷。提供遞迴實現和非遞迴（使用堆疊）實現兩種方式：
:::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 實作迷宮問題：
請輸出 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
Sign in with Wallet
Connect another wallet