---
# System prepended metadata

title: 圖論(graph)

---

# 圖論(Graph Theory)
圖論（Graph Theory）是探討關於圖（Graph）這個數學模型的理論
主要目的是找到如何解決有關於圖（Graph）的問題
以下為圖的範例([source](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E5%AD%A6)#/media/File:6n-graf.svg))：
![image](https://hackmd.io/_uploads/H1R552Og-l.png =70%x)
## 圖的基本
### 結構
圖是由**點（Node）** 與 **邊（Edge）** 所組成
通常以點儲存資料，邊有時會包含**權重（Weight）**，例如走這條邊所需的時間等等

生活中也常有圖的應用，例如家庭成員樹狀圖，其中的邊則代表直系親屬關係，點則表示人名等資訊

### 類型
圖的類型根據邊（Edge）的性質而可先大致分成兩類：**有向圖**與**無向圖**
* **有向圖（directed graph）**：例如 $A$ 可藉由 $\overrightarrow{AB}$ 通往 $B$ ，但 $B$ ==無法==回到 $A$
* **無向圖（undirected graph）**：例如 $A$ 與 $B$ 皆可藉由 $\overline{AB}$ 互通
---
* **有權重圖（weighted graph）**：邊上含有權重
* **無權重圖（unweighted graph）**：邊上無權重 （~~整段很像廢話~~）


另外現階段討論的圖大部分都屬於「**基本圖（simple graph）**，定義如下：
1. 不存在重邊（任兩點間只會有一條邊）
2. 不存在自連邊（不會有邊從自身出發到自身結束）

因此根據以上介紹，頁頂示例圖即為 ||<font color = "f00000">無權重無向圖</font>||

### 其他名詞
#### 度數（degree）
此度數非彼度數，這裡的度數在無向圖中，指的是一個點上有==多少條邊==以自己作為端點；
在有向圖中，度數又分為 **入度（in-degree）** 和 **出度（out-degree）**
* **入度（in-degree）**：有多少邊從==別的點==連到自身
* **出度（out-degree）**：有多少邊從==自身==連到別的點

## 圖的儲存
最常用的儲存方式為使用**鄰接陣列 Adjacency Array**或**鄰接矩陣Adjacency Matrix** 儲存
將 $i$ 點可通往的點，儲存在`array[i]`中
> ps. 若一個點有很多資料要存，可使用不同的資料型態如`pair`或自訂`struct`（詳見：[struct](https://hackmd.io/@WLSH/rywX60IXWl)）

例如輸入 $a, \ b$ 兩點為一無權重==無向圖==中兩點連接，部分程式則可寫為
```cpp
vector<int> adj[SIZE];

...

int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);//雙向
```

以此類推無權重==有向圖==（設 $a$ 走到 $b$）寫法為：
```cpp
vector<int> adj[SIZE];

...

int a, b; cin >> a >> b;
adj[a].push_back(b);//單向
```

## 圖的遍歷- <font color = "FF3F6F">無向圖</font>
有 $N$ 個點、 $M$ 條邊，每條邊連接 $A,\ B$ 兩點
問要從 $X$ 走到 $Y$ 需要幾步？

#### 輸入
第一行有兩個正整數 $N,\ M$，分別代表點與邊的數量，並保證 $1 \le N,\ M \le 100$
接下來有 $M$ 行，每行有兩個正整數 $A、B$（$1 \le A,\ B \le N$），代表兩點互通
最後一行有兩個正整數 $X,\ Y$，代表要從 $X$ 走到 $Y$

#### 輸出
如果可以到達，則輸出一個正整數回答題目所求
反之輸出一個字串 $S$ = `Can't arrive!`

#### 範例輸入1
```
4 3
1 2
3 2
3 4
1 4
```
#### 範例輸出1
```
3
```
#### 範例輸入2
```
7 8
1 2
4 3
6 7
3 6
2 4
7 5
1 3
1 5
1 7
```

#### 範例輸出2
```
2
```

#### 範例輸入3
```
3 1
1 2
1 3
```

#### 範例輸出3
```
Can't arrive!
```

### BFS
:::spoiler Sample Code
```cpp=
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int used[105] = {0}, cnt[105] = {0};

int main(){
    vector<int> adj[105];
    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int x, y; cin >> x >> y;
    used[x] = 1;
    //bfs
    queue<int> q;
    q.push(x);
    while(!q.empty()){
        int npos = q.front(); q.pop();
        for(auto i : adj[npos]){
            if(!used[i]){
                cnt[i] = cnt[npos] + 1;
                used[i] = 1;
                q.push(i);
            }
        }
    }

    if(cnt[y] != 0) cout << cnt[y];
    else cout << "Can't arrive!";
}
```
:::
### DFS
:::spoiler Sample Code
```cpp=
#include <iostream>
#include <vector>
using namespace std;

int used[105] = {0}, ans = INT_MAX;
int x, y;
vector<int> adj[105];

void dfs(int npos, int from, int cnt){
    if(npos == y) {ans = min(ans, cnt); return;}

    for(auto i : adj[npos]){
        if(i == from) continue;

        if(!used[i]){
            used[i] = 1;
            dfs(i, npos, cnt + 1);
            used[i] = 0;
        }
    }
}

int main(){
    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    cin >> x >> y;
    used[x] = 1;
    //dfs
    dfs(x, -1, 0);
    if(ans == INT_MAX) cout << "Can't arrive!";
    else cout << ans;
}
```
:::

## 圖的遍歷- <font color = "FF3F6F">有向圖</font>
有 $N$ 個點、 $M$ 條邊，每條邊連接 $A,\ B$ 兩點，==只能從 $A$ 到 $B$==
問要從 $X$ 走到 $Y$ 需要幾步？

#### 輸入
第一行有兩個正整數 $N,\ M$，分別代表點與邊的數量，並保證 $1 \le M \le N \le 100$
接下來有 $M$ 行，每行有兩個正整數 $A、B$（$1 \le A,\ B \le N$），代表 $A$ 可通往 $B$
最後一行有兩個正整數 $X,\ Y$，代表要從 $X$ 走到 $Y$

#### 輸出
如果可以到達，則輸出一個正整數回答題目所求
反之輸出一個字串 $S$ = `Can't arrive!`

#### 範例輸入1
```
4 3
1 2
2 3
3 4
1 4
```
#### 範例輸出1
```
3
```
#### 範例輸入2
```
7 8
1 2
4 3
6 7
3 6
2 4
7 5
1 3
1 5
1 7
```

#### 範例輸出2
```
3
```

#### 範例輸入3
```
3 2
1 2
3 2
1 3
```

#### 範例輸出3
```
Can't arrive!
```
### BFS
:::spoiler Sample Code
```cpp=
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int used[105] = {0}, cnt[105] = {0};

int main(){
    vector<int> adj[105];
    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        //adj[b].push_back(a);
    }
    int x, y; cin >> x >> y;
    used[x] = 1;
    //bfs
    queue<int> q;
    q.push(x);
    while(!q.empty()){
        int npos = q.front(); q.pop();
        for(auto i : adj[npos]){
            if(!used[i]){
                cnt[i] = cnt[npos] + 1;
                used[i] = 1;
                q.push(i);
            }
        }
    }

    if(cnt[y] != 0) cout << cnt[y];
    else cout << "Can't arrive!";
}
```
:::
### DFS
:::spoiler Sample Code
```cpp=
#include <iostream>
#include <vector>
using namespace std;

int used[105] = {0}, ans = INT_MAX;
int x, y;
vector<int> adj[105];

void dfs(int npos, int from, int cnt){
    if(npos == y) {ans = min(ans, cnt); return;}

    for(auto i : adj[npos]){
        if(i == from) continue;

        if(!used[i]){
            used[i] = 1;
            dfs(i, npos, cnt + 1);
            used[i] = 0;
        }
    }
}

int main(){
    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        //adj[b].push_back(a);
    }
    cin >> x >> y;
    used[x] = 1;
    //dfs
    dfs(x, -1, 0);
    if(ans == INT_MAX) cout << "Can't arrive!";
    else cout << ans;
}
```
:::

## 圖的遍歷- <font color = "FFFF">二維無向圖（$N$ * $M$方格圖）</font>

在某些題目中常見的二維陣列地圖，也是一種無權重無向圖。因此也可以使用BFS或DFS做遍歷，前面已經提過BFS，因此這裡僅說明DFS的遍歷

### BFS
[傳送門](https://hackmd.io/TMBfQGInTUSEfLEpLIaO_Q#BFS%E6%A6%82%E5%BF%B5%E8%AA%AA%E6%98%8E)

### DFS
根據DFS(深度優先搜尋)的概念，跟BFS淹水概念不同的地方是，DFS會選擇一條路走到底，直到不能走或到達終點才回到上一個分岔點找下一條路。
>[!NOTE]DFS(無向圖) 演示圖 
>||(Source：https://zh-yue.wikipedia.org/wiki/File:Depth-First-Search.gif)||
>![image](https://upload.wikimedia.org/wikipedia/commons/7/7f/Depth-First-Search.gif)

可以用DFS的寫法去反推，因為我們到一個條件就會`return`，因此我們會退回上一格，若還有路可以走，則會選擇另一條路繼續「D」下去，以此類推直到`return`回起點

### 實作

#### 輸入
第一行輸入一正整數 $N \leq 20$ 表示 $N * N$ 的地圖
接下來有 $N$ 行，每一行有 $N$ 個數字 $w_1,\ w_2,\ ...\ ,\ w_n \in (0, 1)$
$w_i = 0$ 代表該格不能通過

#### 輸出
輸出一個正整數 $s$ 代表從左上$(0,\ 0)$走到右下$(n-1,\ n-1)$的最短步數

### 思路
可以用DFS的[排組](https://hackmd.io/gBH64XuxQ_SAcHhSxYgaXg#Zerojudge--e446-%E6%8E%92%E5%88%97%E7%94%9F%E6%88%90)寫法去反推，因為我們到一個條件就會`return`，因此我們會退回上一格，若還有路可以走，則會選擇另一條路繼續「D」下去，以此類推直到`return`回起點。
>記得要記錄`used`來判斷是否走過，在`return`後也要還原`used`狀態
>dfs帶著`cnt`走，找最小值

:::spoiler Code
```cpp=
#include <iostream>
using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int n, mp[50][50], used[50][50], mn = INT_MAX;

void dfs(int y, int x, int cnt){
    if(y == n-1 && x == n-1){
        mn = min(mn, cnt);
        return;
    }
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i], nx = x + dx[i];
        if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
        if(used[ny][nx]) continue;
        if(mp[ny][nx] == 0) continue;
        used[ny][nx] = 1;
        dfs(ny, nx, cnt + 1);
        used[ny][nx] = 0;
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> mp[i][j];
        }
    }

    dfs(0, 0, 0);

    cout << mn;
}
```
:::