# NYCU PCCA 2022 Winter Camp 0127
## [圖論](https://www.youtube.com/watch?v=NnM6tCJ_7VQ&list=PLtRlodjJ-YdIizrpGnftvH7hgJEQN7j9E&index=7)
今天的內容只有這個 影片大約2小時

### 圖的介紹
圖 (graph) 是由點(圓圈)跟邊(線條)所成的結構

* 點 Node
* 一個點可以連出去很多邊
* 度數(degree)
入度(x)：有多少點指向點 x 的數量
出度(x)：點 x 向外連接點的數量
* 點上有數字，稱為點權重

* 邊 Edge
* 一條邊只能連到兩個點(相同或相異)
* 邊上有數字，稱為邊權重
* 無方向的邊叫無向邊
有方向的邊叫有向邊

### 圖的存法
#### 1. 鄰接矩陣 Adjacency Matrix
當 A 連到 B 時，陣列中 `array[A][B] = 1, array[B][A] = 1`

##### 存無向邊帶權重
把原本連接的 1 換成權重大小

##### 存有向邊帶權重
假設 A 指向 B，則陣列中 `arr[A][B] = 權重, arr[B][A] = 0`

> code

const int vertex = 1000; // 假設點有 1000 個
int graph[vertex][vertex];
void addEdge(int u, int v, int w) {
    graph[u][v] = w;
    // 存無向邊記得加 graph[v][u] = w;
}

#### 2. 鄰接串列 Adjacency List
就每個點而言，存取和該點連接的所有其他點

##### 存無向邊帶權重
把點和權重一起存取

##### 存有向邊帶權重
假設 A 指向 B，在 A 的串列存 B 和權重，B 的串列則不會有 A 的資料

> code

const int vertex = 1000; // 假設點有 1000 個
struct edge {
    int v, w;
}
vector<edge> graph[vertex];
void addEdge(int u, int v, int w) {
    graph[u].push_back({v, w});
    // 存無向邊記得加 graph[v].push_back({u, w});
}

#### 3. 邊列表 Edge list
就一條邊，存取連接的兩點和權重

> code

struct edge {
    int u, v, w;
}
vector<edge> edgeList;
void addEdge(int u, int v, int w) {
    edgeList.push_back({u, v, w});
}

#### 存法比較
1. **鄰接串列 Adjacency list**
空間複雜度 O(V + E)
2. **鄰接矩陣 Adjacency matrix**
空間複雜度 O(V^2^)
3. **邊列表 Edge list**
空間複雜度 O(E)
:::success
競賽最常用： 鄰接串列
不過每個演算法適合的存取方式也不盡相同 選擇適合的存法是重要的第一步
:::

### 圖的搜索
#### 1. 深度優先搜索(DFS)
* **D**epth **F**irst **S**earch
* 像人在走迷宮
* 先選一條路走
* 走到死路退回來，重選一條路
* 重要的資訊
* In Stamp 入戳章
* Out Stamp 出戳章
> 這兩個資訊可以來解決很多問題
* 大多用遞迴實作，也可以用 Stack
* 說明
▼ 從節點0開始DFS
▼ 選出節點0連出去的邊中還未走訪的點 (節點1)
▼ 選出節點1連出去的邊中還未走訪的點 (節點5)
▼ 以此類推，直到該節點連結的點皆被走訪
▼ 節點2連出去的邊都已經被走訪過了，所以節點2走訪完了，開始往回走
▼ 節點3也走訪完了，繼續往回走
▼ 節點5還有連接到節點4，但是節點4沒有被走訪，所以先去節點4
▼ 節點4也走訪完了，回到節點5
▼ 節點5也走訪完了，繼續往回走
▼ 節點0也走訪完了，DFS結束，取得所有點的 In stamp, Out stamp
* 分析
* 如果使用鄰接串列
* 每個邊跟點只會被掃過一次
* 時間複雜度 O(V+E)
* 如果使用鄰接矩陣
* 每次拜訪每個點都要在花 O(V) 的時間掃過跟每個點是否有邊
* 時間複雜度 O(V^2^)
::: info
實作DFS通常使用時間複雜度較低的鄰接串列
:::
* code

const int vertex = 1000;
int inStamp[vertex], outStamp[vertex], stamp;
vector<int> graph[vertex];
void init() {
    memset(inStamp, 0, sizeof(inStamp);
    memset(outStamp, 0, sizeof(outStamp);
    stamp = 1;
}
void dfs(int u) {
    inStamp = stamp++; // 紀錄in stamp
    for (int v : graph[u]) { // 尋遍所有相鄰的點
        if (inStamp[i] == 0) { // 如果in stamp為0就代表還沒拜訪過
            dfs(i); // 那就拜訪這個點
        }
    }
    outStamp = stamp++; // 紀錄out stamp
}

#### 2. 廣度優先搜索(BFS)
* **B**readth **F**irst **S**earch
* 概念和淹水相同
* 從原點擴散出去
* 重要的資訊
* level值(第幾層)
* 無權重圖中，為該點距離起點的最短路徑
* 搭配 Queue 實作
* 說明
▼ 從節點0開始BFS
▼ 將節點0的level設成0，並丟入queue
▼ 從queue中取最前面的節點(0)，並pop掉該節點
▼ 將節點0相鄰且沒有被拜訪過的點丟進queue，並將該level值+1
▼ 從queue中取最前面的節點(1)，並pop掉該節點
▼ 將節點1相鄰且沒有被拜訪過的點丟進queue，並將該level值+1
▼ 從queue中取最前面的節點(4)，並pop掉該節點
▼ 節點4沒有相鄰且沒被拜訪的點，所以不動作
▼ 重複以上動作，直到queue為空且每個點都走訪完畢，完成BFS。

* 分析
* 如果使用鄰接串列
* 每個邊跟點只會被掃過一次
* 時間複雜度O(V+E)
* 如果使用鄰接矩陣
* 每次拜訪每個點都要在花O(V)的時間掃過跟每個點是否有邊
* 時間複雜度O(V^2^)
::: info
實作BFS通常使用時間複雜度較低的鄰接串列
:::
* code

const int vertex = 1000;
int level[vertex];
vector<int> graph[vertex];
void init() {
    memset(level, -1, sizeof(level);
}
void bfs(int s) {
    queue<int> q;
    q,push(s); // 將起點丟到queue裡面
    level[s] = 0;
    while (q.size()) { // 直到queue是空的才停止
        int u = q.front(); // 拿出queue最前面的節點
        q.pop();
        for (int i : graph[u]) { // 尋遍所有和相鄰的點
            if (level[i] != -1) { // 拜訪過就不動作
                continue;
            }
            level[i] = level[u] + 1; // 更新level
            q.push(i);
        }
    }
}

#### 3. DFS & BFS
* **對圖最基礎的兩個操作**
大部分的演算法都為這兩種操作的組合
* **代價便宜**
如果用Adjaceny list，代價均為線性時間

### 樹
DFS和BFS做完之後，會把一張圖變成一棵樹

這是一棵仿真實世界的樹
但資工的樹通常是反過來的

#### 樹的一些重要名詞
* 根
位於樹的最頂端
* 葉子
位於樹的最底端
* 點和點關係
* 祖先
該點到根的路徑經過的點
* 小孩和爸爸
該點的上一層
* 兄弟姊妹
同一個爸爸
* 子樹
樹的某一部份切下來也會是一棵樹

#### 樹的一些重要性質
* n個點的樹僅有n-1條邊
* 任兩點僅有唯一一條路徑
* 找不到環
> 滿足任兩個性質，第三個就會自動滿足

#### 樹的問題
##### <font size = 3>子樹的size</font>
建立出每一個子樹他的size有多大
例如：
* 方法：一次DFS
▼ 先將每一個節點size值設成1
▼ 從根開始DFS
▼ 遍歷它的小孩們
▼ 往上的時候把小孩的值加給爸爸
▼ DFS結束後，就能得到答案了
* 複雜度分析：
過程只有一次DFS，所以時間複雜度 O(V+E)
* code

const int vertex = 1000;
vector<int> graph[vertex];
int size[vertex];
int dfs(int u, int parent) {
    size[u] = 1; // 初始化每個點的size
    for (int i : graph[u]) { // dfs每個節點
        if (i != parent) {
            size[u] += dfs(i, u); // 把小孩size加進來
        }
    }
    return size[u];
}

##### <font size = 3>最小生成樹</font>
:::success
簡報上的「樹」打成「樹」
交大國文就很差，因為交大資工可以不用看國文，所以講師國文很差滿正常的
:::
給定有權重的聯通圖找出一張子圖，在這張的子圖中選出權重總和最小的生成樹且必須包含所有節點。
例如下圖中綠色的部分，就是這個圖的最小生成樹：
* 方法: Kruskal's algorithm (有點greedy的味道)
將所有的邊依照權重由小到大排序
從最小開始，選擇不會形成環的邊，直到連接所有節點
▼ 用EdgeList方式將所有邊存下來
▼ 將Edgelist依權重由小到大排序，並從最小開始
▼ 將(1, 3)加入不會形成環
▼ 將(2, 3)加入不會形成環
▼ 同樣，將(4, 5)和(3, 4)加入也不會形成環
▼ 但是將(3, 5)加入會形成環，所以不加入
▼ 將(0, 1)加入不會形成環
將(1, 2)、(1, 4)、(0, 2)加入都會形成環，所以都不加入
所以最小生成樹的權重為15
:::warning
使用此方法能保證最小生成樹的權重，但是圖不一定是唯一的
:::
* 複雜度分析
sorting 所以的邊複雜度 O(ElogE)
判斷是否在同一個聯通塊中可以用disjoint set來判斷
總共時間複雜度 O(ElogE)
* code

struct edge {
    int u, v, w;
};
bool cmp(edge a, edge b) {
    return a.w < b.w;
}
vector<edge> edgeList;
int kruksal() {
    int weight = 0;
    sort(edgeList.begin(), edgelist.end(), cmp);
    for (auto i : edgeList) {
        if (merge(i.u, i.v)) { // 判斷u, v是否在同個聯通塊中
            weight += k.w;
        }
    }
    return weight;
}

##### <font size = 3>樹的直徑</font>
找出這棵樹中最長的那條路徑
如下圖：
* 方法：兩次BFS (還可以用DP做)
▼ 隨便對一個點為起點做BFS
▼ 找出離那點最遠的點
▼ 再以該點做一次BFS
▼ S和最遠的點的路徑就是樹直徑
* 複雜度分析
做兩次BFS，時間複雜度O(V+E)
* code
init(), bfs()詳細請回去看BFS的code

int getDiameter() {
    init(); // 初始化
    bfs(0); // 第一次bfs
    int maxLevel = 0, maxIndex = 0;
    for (int i = 0; i < vertex; i++) {
        if (maxLevel < level[i]) {
            maxLevel = level[i];
            maxIndex = i;
        }
    }
    init();
    bfs(maxIndex);
    for (int i = 0; i < vertex; i++) {
        if (maxLevel < level[i]) {
            maxLevel = level[i];
            maxIndex = i;
        }
    }
    return maxLevel;
}

### 有向無環圖 DAG
DAG = Directed Acyclic Graph
#### 拓樸排序 Topological Sort
找出一種在 DAG 上合理的排列順序
以這個DAG為例就是 a b e g h c d f
* 方法：BFS拔拔樂
每次摘掉 1 個 in-degree 為 0 的起點
將它鄰居的 in-degree 都減 1
如果遇到減完後 in-degree 變成 0 的就丟進 queue 裡面
▼ 先計算每個點的 in-degree
▼ 把 in-degree = 0 的點放入 queue (a, g)
▼ 將 queue.front() pop掉，並把pop掉的點放到 topo-sort 裡面
▼ 把與該點相鄰的點 in-degree - 1，如果 in-degree 變 0，就把那個點加入 queue
▼ 一直重複，最後會變成
▼ topo-sort 裡面就是答案
* code

const int MAXN = 1e3 + 5; // 1005
int n;
vector<int> G[MAXN];
int inDegree[MAXN];
void init() {
    memset(inDegree, 0, sizeof(inDegree));
}
void addEdge(int u, int v) {
    G[u].push_back(v);
    inDegree[v]++;
}
void bfsTopo() {
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) { // 如果點的in-degree = 0
            q.push(i); // 把這個點丟進queue
        }
    }
    vector<int> topo;
    while (q.size()) { // queue還沒空就繼續做
        int u = q.front();
        q.pop();
        topo.push_back(u); // 把拔拔樂的點丟進拓樸排序
        for (auto &i : u) {
            inDegree[i]--; // 把和這個點相連的點in-degree - 1
            if (inDegree[i] == 0) { // 如果in-degree變成0
                q.push(i); // 把那個點丟進queue
            }
        }
    }
}

#### 經典問題
##### <font size = 3>DAG最長路</font>
在DAG中找出最長的路徑
* 方法：BFS拔拔樂
▼ 先將所有點的dist設為-1，in-degree為0的點則設為0
▼ 接著把dist = 0的點丟進queue
對和queue裡的點有連接的點做dist[x] = max(dist[x], dist[ parent[x] ] + 1)
並把它們加入queue
以 a 為例：
dist[b] = max(dist[b], dist[a] + 1)
dist[c] = max(dist[c], dist[a] + 1) (b, c會加入queue)
▼ 重複上述步驟，直到尋遍整個圖，就能找到dist最大的為最長路

##### <font size = 3>DAG最短路</font>
在DAG中給定一個點，找到該點對任何一點的最短距離
* 方法：BFS拔拔樂
▼ 假設a為起點，將a的dist設為0，其他點設為無限大，並把a加入queue
▼ 取queue最前面的點
對該點連接的點做dist[x] = min(dist[x], dist[ parent[x] ] + 1)
之後把有連接的點加入queue
▼ 重複上述步驟，直到尋遍整個圖
可以發現到下圖中g的dist是無限大，這表示從a點無法走到g
:::info
BFS拔拔樂可以適用於DAG各點權重不同的情況(包含最長&最短路)
:::

##### <font size = 3>一般圖呢？</font>
一般圖因為有環，所以不能使用BFS拔拔樂
( 環上每點的in-degree都不會是0 )
那該怎麼辦？
* relaxation操作
* 原本已知最短路徑如下：
* 找到一條更短的路，讓當前最短路更短了
* dis[i]為從原點到 i 的當前最短路徑
* dis[v] = min(dis[v], dis[u] + cost(w, v))
* Djikstra演算法
貪心性質，如果該節點距離是尚未被選取的點中最小的，那他就是最短路徑
我們可以透過這個最短路做relaxation，維護其他邊
▼ 假設0是起點，初始化dis陣列 (dis[i] = 起點到i的距離)
▼ 選出最小的 dis[i] (節點0)，並對他的鄰居做relaxation操作
▼ 選出最小的 dis[i] (節點1)，並對他的鄰居做relaxation操作
▼ 選出最小的 dis[i] (節點3)，並對他的鄰居做relaxation操作
▼ 選出最小的 dis[i] (節點2)，並對他的鄰居做relaxation操作
▼ 選出最小的 dis[i] (節點4)，沒有鄰居不動作
▼ 選出最小的 dis[i] (節點5)，沒有鄰居不動作
所有點都選到了，Dijkstra結束
* 實作
* 每次都挑選當前dis陣列中最小的節點
:::spoiler 需要一個可以支援插入新東西並排好序的 (先想想看再點開看答案)
priority queue
:::
* 複雜度分析
最壞的情況每個點每個邊都需要被丟進 priority queue
O((E+V)logV)
* code

    struct edge {
        int v, w;
        bool operator <(const edge &cmp) const {
            return cmp.w < w; // 定義edge的排序方式(小到大)
        }
    };
    vector<edge> graph[1000];
    int dis[1000];
    void dijkstra(int s) {
        memset(dis, 0, sizeof(dis));
        priority_queue<edge> pq;
        pq.push({s, 0});
        while (pq.size()) {
            auto node = pq.front();
            pq.pop();
            if (dis[node.v] != -1) continue; // node.v在之前就更新過了
            dis[node.v] = node.w;
            for (auto k : graph[node.v]) { // 列舉所有相鄰的邊
                if (dis[k.v] == -1) { // relaxation操作
                    pq.push({k.v, k.w + node.w});
                }
            }
        }
    }

* Bellman-Ford 演算法
* 每一回合都讓每條邊都relaxation一次
* 做 n - 1 回合就完成單源點最短路
* 適用於任何的圖

用 Edge List 的方式存起來 (Adjacency List也可以，作法大同小異)，初始化dis陣列
對第一條邊做relaxation操作
對第二條邊做relaxation操作
對第三條邊做relaxation操作
對第四條邊做relaxation操作
對第五條邊做relaxation操作
對第六條邊做relaxation操作
對第七條邊做relaxation操作
對第八條邊做relaxation操作，完成第一回合
完成第 n - 1 回合之後，就能找到最短路
* 為什麼最多要做要做 n - 1 次
* n 個點的圖中的路徑最多經過 n 個點 (每個點都走到)
* 每一次relaxation最多讓當前最短路徑多增加一個點
* 因此每個點最多需要做 n - 1 次的relaxation才會形成 n 個點的路徑
* 複雜度分析
* 一次relaxation的cost為 O(1)
* 每一回合都會做O(E)次 relaxation
* 總共要做O(V - 1)回合

**總共是 O((V - 1) * E * 1) = O(VE)**

* code

const long long inf = 1e18;
cinst int maxn = 1000;
int n, dis[maxn];
vector<edge> edgeList; // 邊列表
void bellmanFord(int s) {
    for (int i = 0; i < maxn; i++) dis[i] = inf;
    dis[s] = 0;
    for (int i = 0; i < n - 1; i++) { // n - 1次
        for (auto e : edgeList) { // 每次都跑全部的邊
            dis[e.v] = min(dis[e.v], dis[e.u] + e.w); // relaxation操作
        }
    }
}

##### <font size = 3>負權重的一般圖呢？</font>
Dijkstra 不行 (貪心性質不會成立)
BellmanFord 不一定，因為：
* 負環
* 找到一個環，他的總和是負數
* 在有負環的圖中，多繞幾圈他會形成更短的路徑
所以**不存在最短路徑**
:::info
若圖沒有出現可以到達的負環，BellmanFord依然可以照常運作。
:::
* 用 Bellman Ford 偵測負環
* Bellman Ford 在沒有負環的圖做 n - 1 次的迭代就會收斂
做 n - 1 次迭代還沒有收斂，表示有負環
* 紀錄每個點被更新幾次，更新超過 n - 1 次代表這張圖有負環
* code

const long long inf = 1e18;
cinst int maxn = 1000;
int n, dis[maxn];
vector<edge> edgeList;
bool negativeCycle() {
    for (int i = 0; i < maxn; i++) dis[i] = 0;
    for (int i = 0; i < n; i++) { // 原本做n - 1次
        for (auto e : edgeList) {
            if (dist[e.v] > dist[e.u] + e.w) {
                dist[e.v] = dist[e.u] + e.w;
                if (i == n - 1) return true; // 如果n - 1次之後還有更新就代表有負環
            }
        }
    }
    return false;
}

##### <font size = 3>一般圖全點對最短路徑</font>
* 如果圖為正值權，那就做V次dijstra複雜度 O( V(E+V)logV )
* 如果圖為負值權，那就做V次bellman Ford複雜度 O( EV^2^ )
:::danger
<font size = 5>但但但！！！！！！</font>
如果圖為完全圖 E = V^2
正值權複雜度O(V^3lgV)
負值權為O(V^4)
:::
再看一下relaxation的式子dis[v] = min(dis[v], dis[k] + dis(k, v))
我們改寫一下式子讓dis[u][v]為u到v的最短距離
dis[u][v] = min(dis[u][v], dis[u][k] + dis(k, v))
有沒有發現這個**很像dp式！**
dp(k, u, v) 為利用前k個節點relaxation後的結果
**dp(k + 1, u, v) = min{dp(k, u, v), dp(k, u, k + 1) + dp(k, k + 1, v)}**
其實討論 k + 1 的時候只需要用到 k 的部分所以可以重複使用 dis 陣列！！！
這就是 ==floyd warshall 演算法==
* code

int vertex = 100;
int dis[vertex][vertex];
for (int i = 0; i < vertex; i++) {
    for (int j = 0; j < vertex; j++) {
        for (int k = 0; k < vertex; k++) {
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        }
    }
}

* 複雜度分析 O(V^3^)

### 延伸題材
* 割點和橋
* 樹上LCA
* 各種連通分量
* 點雙連通、邊雙連通、強連通分量
* 配對問題
* 最大流與最小割
* 最大團與最大獨立集
* 一筆劃問題
* . . . . . .

### 課後練習
[Formula 1](https://oj.nctu.edu.tw/problems/1391/)
[Mad mobile phone gamer !](https://oj.nctu.edu.tw/problems/1393/)
[Deducting Weights](https://oj.nctu.edu.tw/problems/1396/)
[Drug Dealer](https://oj.nctu.edu.tw/problems/1392/)
[Building Highways](https://oj.nctu.edu.tw/problems/1389/)
[Time Machine Network](https://oj.nctu.edu.tw/problems/1397/)
[TIOJ 1509 . 地道問題](https://tioj.ck.tp.edu.tw/problems/1509)
[Problem - 938D - Codeforces](https://codeforces.com/problemset/problem/938/D)
[Problem - 1463E - Codeforces](https://codeforces.com/contest/1463/problem/E)