## 基本概念
### 圖的定義
圖是用節點(Vertex, $V$ ) 跟邊(Edge, $E$ ) 組成的圖形
兩點之間可以**用邊互相連接起來**，由許多點跟邊組成的集合 $G$ 就是圖，可以表示為 $G=(V,E)$
點(節點)可以用來表示很多事物，題目中最常見的有城市、人物、站點等等
此時的邊則是會表示城市之間的道路、人物的關係、站點之前連接的軌道等等
邊還可以分為**有方向**或是**沒有方向**，例如上圖就是**無向邊**
有向邊通常會用箭頭表示邊的方向，而具有有向邊的圖稱為**有向圖**，而**無向圖**跟上圖一樣
邊還可以賦予權重 (weight)，用來表達**邊的特性**
舉個例子 :
假如現在頂點代表城市，而邊代表城市之間的道路，如果是有向圖的話，可能道路就會是**單行道**
如果邊還具有權重，權重可能是**兩城市之間的距離**，或是其他限制

---
然後如果想在解題的過程中畫圖，這裡推薦一個[網站](https://graphonline.top/)，有英文跟簡體中文

### 相關名詞介紹(查找表)
這裡是用於查找的功效，類似工具書，不用先知道
* 相鄰 (adjacent) : $U,\ V$ 兩點間有邊相連，則稱 $U,\ V$ 兩點相鄰
* 度 (degree) : 某點有多少相鄰的點(連接的邊數)，則為多少度，為 $deg(V)$
* 入邊 (in-degree) : 指向節點的邊數量，為 $deg^+(V)$
* 出邊 (out-degree) : 從節點往外指的邊數量，為 $deg_-(V)$

(注意無向圖沒有入邊出邊，因為邊沒有指向)
* 孤立點 (isolated vertex) : $deg(V) = 0$
* 偶點 (even vertex)： $2\ |\ deg(v)$
* 奇點 (odd vertex)： $1\ |\ deg(v)$
* 葉節點 (leaf vertex)： $deg(v) = 1$

### 邊相關名詞
1. 權重 (weight) : 計為 $w(U,V)$，可以是負數(稱為負邊)
2. 重邊 (multipul edge)：兩條**一模一樣**的邊
3. 路徑 (path)：由一個點到另一個點所**經過的邊**
4. 簡單路徑 (simple path)：路徑上每個點只走過一次
5. 最短路徑 (shortest path)：最少權重和或最短的路徑
6. 環、迴路 (cycle)：一條**起終點相同**的路徑
7. 自環 (self-cycle)：自己連到自己的環
8. 負環 (negative cycle)：**權重和為負**的環
9. 連通 (connected) : 等等介紹

### 連通
在無向圖中，存在一條路徑能夠從 $U$ 走到 $V$，稱為兩點**連通**
而如果其中有多個不相互連接的區塊，則每一個區塊稱為**連通分量**

在有向圖中，因為存在一條路徑能夠從從 $U$ 走到 $V$，不代表
能夠從從 $V$ 走到 $U$
所以如果兩點能夠完全互通(兩者皆可以到另外一點)，稱為**強連通**
而在圖中某一區塊能夠兩兩完全互通，稱為**強連通區塊**
如果兩點間**必須**要把邊改成無向才能連通，稱為**弱連通**

### 種類
1. 簡單圖 : 沒有自環或重邊的圖
2. 有向圖、無向圖、混和圖(有些有向，有些無向)
3. 子圖 : 由一張圖內的某些點、邊組成的圖
4. 稀疏圖、稠密圖 : 若 $|\ E\ |$ 遠小於 $|\ V\ |^2$ 稱為稀疏圖，反之為稠密圖
5. 有向無環圖 (DAG)(Directed Acyclic Graph): 沒有環的有向圖
6. 樹 : $n$ 個節點，$n − 1$ 條邊的有向無環圖

## basic 一筆畫問題
有一張無向圖，求有沒有辦法在每條邊不經過兩次的情況下，將所有點跟邊都走過一遍
比如下方的圖，從任一個線段的交點開始，是否能夠一筆畫畫出整個圖形

解題思路 :
如果一張圖能夠一筆畫走訪會有兩種情況，一種是起點與終點一樣，一個是起點與終點不同
第一種可以想像一個正方形，從各頂點開始畫線，都會回到起點，第二種想像一條直線
那對於第一種情況來說，起點跟終點相同，所以將起點跟其他點相同，進入+出去的次數只會是偶數
而對於第二種情況，起點/偶數進入+出去的次數都是奇數，其他點則是偶數
最後得到結論，奇點(進入+出去的次數為奇數)的數量只能是 $0$ 或 $2$
所以這題可以一筆畫畫出，其他的題目也可以用同樣的邏輯解

## 圖的表示方法
圖是由邊跟點組成的，如果只要記錄點，使用一維陣列即可
但是如果加上邊，最少會需要同時儲存兩個點的資料 :
1. 與邊連接的點 A
2. 與邊連接的點 B

這時候就不能使用一維陣列去儲存資料了，以下會介紹兩種常見的方法
1. 相鄰矩陣(Adjacency Matrix)
2. 相鄰串列(Adjacency List)

### 相鄰矩陣(Adjacency Matrix)
使用相鄰矩陣時，需要用到一個二維陣列，其大小是 : (點數量 × 點數量)
而當中 $G[i][j]$ 的意義是表示有方向性的邊從點 $i$ 連接到點 $j$
當然也可以用來表達無方向性的邊，只要將 $G[i][j]$ 和 $G[j][i]$ 都設定值就可以了
而二維陣列的資料型態通常是依據**有沒有邊權重**決定的
如果有邊權重，那就使用 int 去表示權重，用 $0$ 或是其他非題目範圍內數字表示沒有邊連接
如果沒有邊權重，那只要使用 bool 去表示有沒有邊即可
此時時間複雜度如下(點數量為 $V$，邊數量為 $E$) :
* 查詢點 $A$ 到點 $B$ 是否存在邊 : $O(1)$
* 查找一個點的出(入)邊 : $O(V)$
* 跑過整張圖(圖的遍歷) : $O(V^2)$
* 空間複雜度 : $O(V^2)$

應該很容易發現，只要點的數量過多，但是邊的數量較少時，會有很多空間與時間浪費
實際經驗大概 $V > 4000$ 就不太行了，所以這個方法很少用在 $V$ 比較大的情況
通常在需要遍歷所有邊的情況下也不會考慮這個方式，因為時間複雜度太大了
以下是一個無向、無權重的圖例

bool G[1005][1005] = {} ; // 圖的初始化
 
int main() {
    int e ;
    cin >> e ;
    for (int i=0, a, b;i<e;i++) {
        cin >> a >> b ;
        G[a][b] = true ; 
        G[b][a] = true ; // 代表此範例是無向無權重邊
    }
    return 0 ;
}

### 相鄰串列(Adjacency List)
上面說到的相鄰陣列在極端的情況下會變得很難用，比如有 $1000$ 個點，但只有 $1$ 個邊
跑過整張圖還是要花費 $1000\times1000$，所以相鄰串列就出現了
相鄰串列的特點就是可以只儲存輸入的邊，而不會造成空間的浪費
既然不能提前預知點 $A$ 有幾個連接的邊，就會用到動態新增或修改的功能
一般來說會用 Linked List 去做，但為了方便在 C++ 使用 vector 實作
以下一樣是無向、無權重的圖例

int v, e ; // 點的數量跟邊的數量
cin >> v >> e ;

vector <int> G[v] ;
for (int i=0, a, b;i<e;i++) {
    cin >> a >> b ;
    G[a].push_back(b) ;
    G[b].push_back(a) ;
}

如果有邊權重就用 struct 或是 pair (一個放點，一個放權重) 做 vector 的內置資料型態
如果同時有邊權重跟方向就只能用 struct 做 vector 的內置資料型態
此時的複雜度會如下(點數量為 $V$，邊數量為 $E$) :
* 查詢點 $A$ 到點 $B$ 是否存在邊 : $O(deg^+(A))$
* 查找一個點 $A$ 的出邊 : $O(deg^+(A))$
* 跑過整張圖(圖的遍歷) : $O(E)$
* 空間複雜度 : $O(E)$

如果將邊進行排序之後查詢也可以使用二分搜(需排列)進一步將複雜度壓縮到 $O(log\ deg^+(A))$
以上的複雜度在所有圖論的題目當中**都不算過大**，所以也最常被使用在圖論相關的題目

---
除此之外還有一種表示方法 edge list，通常是題目給定的方法
簡單講就是給予 $m$ 個邊，每個邊都是 $(a,b)$，表示 $a$ 和 $b$ 之間有邊

## CF round 810 B.Party
[題目連結(英文)](https://codeforces.com/contest/1711/problem/B)
Cody 非常喜歡辦派對，他有一張 $n$ 個人的名單，當第 $i$ 個人沒被邀請到時，$uv$ 就會增加 $a_i$
在這 $n$ 個人中，有 $m$ 對朋友關係，如果第 $p_i$ 對關係中的兩個人都被邀請到，那他們就會一起吃一個蛋糕
因為 Cody 是很注重他人朋友關係的人，只要有被邀請，吃掉的蛋糕總數將等於朋友對關係的數量
Cody 更重視食物浪費，寧願不邀請朋友，也不要浪費食物
而且 Cody 的烤箱一次只能烤兩個蛋糕 (也就是不能單獨烤一個，也不能剩下)
想請問你派對中最小可能的 $uv$ 是多少 ?
輸入說明 : 第一行是 $n\ m$，第二行是 $n$ 個朋友沒來的 $uv$ 值，接下來 $m$ 行代表 $m$ 對朋友關係

範例輸入 :
5 5
1 2 3 4 5
1 2
1 3
1 4
1 5
2 3
(因為有五個朋友對關係，所以如果邀請五個人，蛋糕需要 $5$ 個，但是 Cody 最討厭食物浪費
所以必須要剔除某些人的名額，在這個範例測資中，不考慮 $uv$、邀請四個人的情況下
選擇踢掉 $4$，此時的朋友關係對 $=\ {(1,2),(1,3),(1,5),(2,3)}$ 共四對
選擇踢掉 $5$，此時的朋友關係對 $=\ {(1,2),(1,3),(1,4),(2,3)}$ 共四對
在這個範例測資中，不考慮 $uv$、邀請三個人的情況下
選擇踢掉 $1,2$，此時的朋友關係對 $= 0$，也就是沒有朋友
還有其他可能但不列出來，最後只要看總 $uv$ 值做出選擇就好)

範例輸出 :
3

解題思路 :
可以先把每個朋友當作一個點，每個朋友關係對當作邊，也就是說少邀請一個朋友
也就是少了所有跟那個點連接的邊，而且有些情況根本不用刪點
在當前朋友對關係是偶數下，蛋糕不會剩，並且每個朋友關係對都有一個蛋糕
所以不需要少邀請誰，也就是 $uv$ 值 $=\ 0$
如果目前邊數(目前朋友關係對數量)是奇數的情況就要透過刪點的方式
把邊數縮減到偶數的情況才可以開始分蛋糕，如果有點是奇數邊
我們就可以考慮刪除它，也就是找最小 $uv$ 總和的奇點
但是如果在沒有奇點的圖(皆偶點但奇數邊)上考慮刪點
這時候先考慮刪掉某點後的情況，如果刪掉點 $U$，此時跟 $U$ 連接的點都會變成奇點
這時候只要再刪除一個奇點就可以讓邊數回到偶數

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

int cost[100005] ; // 不開心值
int deg[100005] ; // 點 i 有幾個邊
pair <int, int> edge[100005] ; 
// 邊的儲存(因為題目只需要知道哪點跟哪點之間有連接，所以不需要用之前教的方法)

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ; // I/O 加速
    
    int n, m ;
    cin >> n >> m ; 
    for (int i=1;i<=n;i++) 
        deg[i] = 0, cin >> cost[i] ; 
    
    for (int i=1, a, b;i<=m;i++) {
        cin >> a >> b ;
        deg[a]++, deg[b]++ ; // 新增邊數
        edge[i] = {a,b} ; // 新增邊
    }

    if (m&1 == 0) {    // m 是偶數
        cout << "0\n" ;
        return 0 ;
    }

    int ans = INT_MAX ; // 最大數值
    for (int i=1;i<=n;i++)
        if (deg[i] & 1) // 找奇點
            ans = min(ans, cost[i]) ;

    for (int i=1;i<=m;i++) {
        int e_f = edge[i].first, e_s = edge[i].second ; // 第 i 個朋友關係對
        if ((deg[e_f]&1) == 0 && (deg[e_s]&1) == 0) { // 看是不是都是偶點
            ans = min(ans, cost[e_f]+cost[e_s]) ;
        }
    }
    cout << ans << '\n' ;
}

## 跑過整張圖(圖的遍歷)
要遍歷整張圖，或是想要從某點 $A$ 走到所有連通的點，通常會使用兩個方法
BFS(廣度優先搜尋) 和 DFS(深度優先搜尋)，兩者的定義跟區別都會在[這個篇章](/r1CZ09Gyxl)介紹
不過要記得，走過所有的點不代表走過所有的邊，因為有些圖不一定只有一條路可以走

## 節點相關計算
基本上在記錄圖的過程中，就可以知道節點的度數、鄰居數量
如果是有向圖，會更詳細區分成入邊數量(in-degree)、出邊數量/鄰居數量(out-degree)

int n = 26, e = 16, a, b ;
int ind[26], outd[26] ;
for (int i=0;i<e;i++) {
    cin >> a >> b ;
    ind[b]++ ;
    outd[a]++ ;
}

在無向圖中節點度數就是與節點相連邊數量，也是鄰居數量

## 節點距離計算
兩點之間的某一路徑，這條路徑的邊數量為最小，這條路徑的邊數量就是所謂兩點之間的距離
這種考慮最少邊的路徑，會使用 BFS，因為 BFS 的概念就是每次都處理與原節點相同距離的節點
所以只要從原節點做 BFS 遇到任何點的步數，都會是原節點到該節點的距離

#include<bits/stdc++.h>
using namespace std ;
typedef pair<int, int> Pii ;
#define FF first
#define SS second

int main() {
    ios::sync_with_stdio(0), cin.tie(0) ;

    int n, m ; //  n nodes, m edges
    cin >> n >> m ;

    vector<int> G[n] ; // Adjacency List
    for (int i=0;i<m;i++) {
        int a, b ;
        cin >> a >> b ;

        // add new edge
        G[a].push_back(b) ;
    }

    int a, b, ans = -1 ; // distance from a to b is ans
    cin >> a >> b ;
    if (a == b) {
        cout << "0\n" ;
        return 0 ;
    }

    // using bfs to find ans
    vector<bool> gone(n, false) ; // gone[i] means if node i be gone or not
    queue<Pii> que ;
    que.push({a, 1}) ; // a is start
    gone[a] = true ;
    while (!que.empty()) {
        Pii now = que.front() ;

        if (now.FF == b) {
            ans = now.SS ;
            break ;
        }
        for (int &it: G[now.FF]) { // it is a node which connect node now.FF
            if (!gone[it]) {
                gone[it] = true ;
                que.push({it, now.SS+1}) ;
            }
        }
    }

    if (ans != -1)
        cout << ans << '\n' ;
    else
        cout << "a can't connect b." ;

    return 0 ;
}

注意這裡的距離不是邊權重的距離，如果要找到最小邊權重總和的話，需要其他進階的演算法

## 子父圖概念
在考慮某一張圖 $G$，刪除某一些節點或刪除某一些邊之後，就是 $G$ 的子圖
如果是 $G$ (沒有刪除)或是空圖(將節點與邊全部刪除)也算子圖
(注意這裡如果刪除某節點表示與該節點相關的邊都會被刪除)
如果 $G$ 新增一些節點或新增一些邊，就是 $G$ 的父圖，$G$ 也是自身的父圖

## 例題-TIOJ 1152 銀河帝國旅行社
[題目連結](https://tioj.ck.tp.edu.tw/problems/1152)
在最先介紹 DFS 時有一個例題是關於星球間的最大距離，題目敘述跟樹有關
但這題其實不需要學過樹也可以解，以下是不用把圖轉換成樹的解法
銀河帝國有 $n$ 個星球，每個星球都有從屬關係，只有數字小的才可以當數字大的主星
每個星球保證有一個主星，唯獨帝國首都(代號 $0$)沒有主星，有些星球沒有屬星只有主星
並且保證不會出現從屬關係混亂的情況(例如: $S_1$ 是 $S_2$ 的主星，$S_0$ 是 $S_1$ 的主星，$S_2$ 是 $S_0$ 的主星)
也就是不會出現環的情況，並保證從屬關係至多 $10^4$ 層，問任兩點之間最遠距離為多少
第一行為 $n$，接下來 $n$ 行為第 $i$ 個星球的屬星，並且以 $-1$ 當作結尾
$i$ 的範圍是 $0\sim n-1$，如果是單一一行的 $-1$，代表該星球沒有屬星

範例輸入 :
5
1 2 -1
3 -1
4 -1
-1
-1

範例輸出 :
4

題目解析 :
在題目當中，從屬星的關係就跟父子節點關係相同，當中的某些條件正好對應到樹的特性
"每個星球保證有一個主星，唯獨帝國首都(代號 $0$ )沒有主星"
就是除了樹根，每個點都有父節點，不會出現環也是樹的特性
下一段會整理+舉例樹的所有特性，讓各位能更清晰地理解
總之任兩點之間最長的距離也就是樹的直徑，解法這裡不贅述

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

int dfs(int now, vector<vector<int>> &G) {
    int h = 0 ;
    for (int &it: G[now])
        h = max(h, dfs(it, G)+1) ;

    return h ;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;

    int n, tmp ;
    cin >> n ;
    vector<vector<int>> G(n) ;

    for (int i=0;i<n;i++)
        while (cin >> tmp && tmp != -1) // 輸入資料，遇到-1結束
            G[i].push_back(tmp) ;

    int h1 = 0, h2 = 0 ; // 需保證 h1 >= h2
    for (int &it: G[0]) {
        tmp = dfs(it, G)+1 ;
        if (tmp > h1) { // 找到目前最大高度
            h2 = h1 ;
            h1 = tmp ;
        }
        else if (tmp > h2) // 找到目前第二大高度
            h2 = tmp ;
    }

    cout << h1+h2 ;

    return 0 ;
}

## 例題-ZJ a753. 一、最大面積
[題目連結](https://zerojudge.tw/ShowProblem?problemid=a753)
在一個 $A\times B$ 的矩形區域內，每一個子區域用正整數表示區域內的高度，每一個子區域的面積為 $1$
我們想要知道的是，高度 $H$ 的”連續”面積，最大是多少
所謂連續就是某點跟其上下左右點的數值相同
(詳細輸入/輸出說明請看連結)

範例輸入 :
5 7
1 1 1 4 1 1 1
1 2 2 3 1 3 1
1 2 3 3 3 1 1
2 2 3 3 2 2 2
4 3 2 2 1 2 2
4
1
2
3
4

範例輸出 :
7
5
6
0

解題思路 :
這題只要用 BFS 去找不同數字的最大面積就可以了

#include<bits/stdc++.h>
using namespace std ;
typedef pair<int, int> Pii ;
#define FF first
#define SS second

int main() {
    ios::sync_with_stdio(0), cin.tie(0) ;

    int mm[4][2] = {0,1, 0,-1, 1,0, -1,0} ; // 四個方向
    int n, m ;
    cin >> n >> m ;

    vector<int> tmp(m) ;
    vector<vector<int>> G(n, tmp) ;

    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            cin >> G[i][j] ;

    vector<int> ans(10, 0) ; // 一次計算完 1~9 最大面積
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (G[i][j] == -1) continue ; // 走過了

            int num = G[i][j], cnt = 1 ; // 目前數字 數字數量
            
            // BFS
            queue<Pii> que ;
            que.push({i, j}) ;
            G[i][j] = -1 ;
            while (!que.empty()) {
                Pii now = que.front() ;
                que.pop() ;

                for (int k=0;k<4;k++) { // 四個方向
                    int nx = now.FF+mm[k][0], ny = now.SS+mm[k][1] ;
                    if (nx < n && nx >= 0 && ny < m && ny >= 0) {
                        if(G[nx][ny] != num) continue ;
                        que.push({nx, ny}) ;
                        G[nx][ny] = -1 ;
                        cnt++ ;
                    }
                }
            }
            if (cnt < 2) cnt = 0 ; // 小於 2 等於沒有連續面積
            ans[num] = max(ans[num], cnt) ;
        }
    }
    
    // 輸出
    int a, b ;
    cin >> a ;
    for (int i=0;i<a;i++) {
        cin >> b ;
        cout << ans[b] << '\n' ;
    }

    return 0 ;
}