<style>
.reveal .slides {
text-align: left;
font-size:35px
}
</style>
# 圖論
Introduction to Competitive Programming
2/9
----
- 名詞介紹
- 建圖方法(矩陣, 鄰接表[vector])
- 圖上 DFS/BFS 怎麼遍歷
- 樹上 DFS/BFS 怎麼遍歷
- 樹的基本演算法
- 樹經典例題
----
## 名詞介紹
(以下內容也都會在資工其他領域學習到
----
- 圖(graph)：由一些點與一些邊所組成，通常以$G=(V,E)表示$
- 點(vertex)：節點，通常以$V$表示
- 邊(edge)：連接兩點，通常以$E$表示，$e=(u,v)$ 代表邊$e$連接$u,v$兩點，也就是$u,v$為$e$的端點
----
## 相關用語定義
- 權重(weight)：指圖的點/邊附帶的數值
- 點數/邊數：點/邊的數量，通常記為$V/E(n/m)$
- 有向邊：邊可以分為無向邊(雙向)與有向邊(單向)
- 重邊(multiple edge)：指兩點之間有多條邊連接
- 自環(self loop)：指兩端為同一點的邊$e=(u,u)$
- 度數(degree)：一個點所連接的邊的數量，若是有向邊則又分為出度與入度
- 相鄰(adjacent)：指兩個點間有無向邊相連
- 指向(consecutive)：有向邊的起點"指向"終點
----
## 更多的定義
- 路徑(path)：從起始點到目標點上所經過的所有點，路徑上的點/邊皆可重複
- 行跡(trace)：邊不重複的路徑
- 迴路(circuit)：邊不重複且起終點相同的路徑
- 簡單路徑(track)：點不重複的路徑
- 環(cycle)：點不重複且起終點相同的路徑
- 連通(connected)：$u,v$連通若且唯若存在$u到v$或$v到u$的路徑，一群點連通代表這群點兩兩連通
----
## 各種圖的定義
- 簡單圖(simple graph)：沒有重邊與自環的圖
- 無向圖(undirected graph)/有向圖(directed graph)：只有無向邊/有向邊的圖
- 連通圖(connected graph)：任兩點皆連通的圖
- 樹(tree)：無向無環連通圖(其實也可以有向)
- 森林(forest)：每個連通分量（連通塊）都是樹的圖。按照定義，一棵樹也是森林
- 完全圖(complete graph)：任兩點都相鄰的圖
- 有向無環圖(directed acyclic graph,DAG)：...
- 二分圖(bipartite graph)：圖上的點可以分為兩群$U,V$使得同群點之間皆不相鄰
----
## 圖之間關係的定義
- 子圖(subgraph)：邊/點皆為原圖的子集
- 補圖(complement graph)：若兩張圖點集相同，邊集互斥且聯集為完全圖，則兩張圖互為補圖
- 同構(isomorphic)：不考慮編號長的完全相同的圖
- 生成樹(spanning tree)：點集相同且為樹的子圖
----
## 對於有根樹的定義
- 父親(parent node)：對於除根以外的每個結點，定義為從該結點到根路徑上的第二個結點。 根結點沒有父結點。
- 祖先(ancestor)：一個結點到根結點的路徑上，除了它本身外的結點。 根結點的祖先集合為空。
- 子結點(child node)：如果 u 是 v 的父親，那麽 v 是 u 的子結點。
- 結點的深度(depth)：到根結點的路徑上的邊數。
- 樹的高度(height)：所有結點的深度的最大值。
- 兄弟(sibling)：同一個父親的多個子結點互為兄弟。
- 後代(descendant)：子結點和子結點的後代。
- 子樹(subtree)：刪掉與父親相連的邊後，該結點所在的子圖。
----
## 進階圖這堂課則不討論
---
# 下課時間
---
## 建圖方式
* 矩陣建圖
* 鄰接表[vector]
* 邊建圖(很少用到因此不教)
----
## 矩陣建圖(鄰接矩陣)
- $n\times n$的矩陣，其中$A_{ij}$代表點$i$是否連通或是指向點$j$
- 若為帶權圖則$A_{ij}$存$i$到$j$的邊權
- 若圖有重邊也可以令$A_{ij}$存邊$(i,j)$的數量
- 空間複雜度$O(n^2)$
- 遍歷圖的時間複雜度$O(n^2)$
- 由於複雜度高因此不常用
----
## 鄰接表[vector] (鄰接串列)
- $n$個串列，第$i$個串列存$i$所指向的邊(點)
- 若為帶權圖，則串列可以存pair(目標點,邊權)
- 通常以vector取代串列，也就是vector陣列或二維vector
- 空間複雜度$O(m)$
- 遍歷圖的時間複雜度$O(m)$
- 最常使用的儲存方式
---
## 深度優先搜索(Depth-First Search,DFS)
- 優先往深的地方走
- 通常以遞迴實作，直觀好寫(也可以使用stack取代遞迴)
- 時間複雜度$O(E)$(若用鄰接串列)
- 由於好寫，以及遞迴方便維護，有很多好的性質，因此是最常用的搜索方法
- 然而遞迴過深有可能導致stack overflow(RE)，遇到時只得改成用迴圈+stack實作(或一些毒瘤方法)
----
## 實作範例
```cpp
void dfs(int x){
vis[x]=1;
for(int i:edge[x]){
if(!vis[i])
dfs(i);
}
}
```
----
## 廣度優先搜索(Breadth-First Search,BFS)
- 從起點開始往外散開
- 以迴圈+queue實作，寫起來較麻煩
- 對於無權圖，BFS可找出到起點的最短路徑
- 時間複雜度$O(E)$(若用鄰接串列)
- 由於較難寫因此較少用，常用在找不帶權最短路
----
```cpp
void bfs(int s){
queue<int> q;
q.push(s);
vis[s]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int i:edge[x]){
if(!vis[i])
q.push(i),vis[i]=1;
}
}
}
```
---
## 樹上DFS
由於沒有環，只要不要走回頭路就不會走到重複的點，因此多傳遞一個參數"父節點"就不需要visit陣列判斷點是否造訪過
----
```cpp
void dfs(int x,int father){
for(int i:edge[x]){
if(i!=father)
dfs(i,x);
}
}
```
----
## 樹上BFS
由於沒有環，只要不要走回頭路就不會走到重複的點，因此多傳遞一個參數"父節點"就不需要visit陣列判斷點是否造訪過(as DFS)
從樹根開始，嚴格按照層次來訪問節點。
BFS 過程中也可以順便求出各個節點的深度和父親節點。
----
```cpp
void bfs(int s){
queue<pair<int,int>> q;
q.push(make_pair(s,0));
while(!q.empty()){
auto [x,y]=q.front();q.pop();
for(int i:vec[x])
if(i!=y)
q.push(make_pair(i,x));
}
}
```
---
## 樹的基本演算法
----
### 深度
求出一棵有根樹每個節點的深度
- 子節點深度為父節點+1(或邊權)
- 根節點的深度為0(或1，視題目要求)
```cpp
void dfs(int x,int father)
{
for(int i:edge[x])
{
if(i!=father)
d[i]=d[x]+1,dfs(i,x);
}
}
```
----
### 高度
求出一棵有根樹每個節點的高度
- 一個點的高度為所有子節點中，高度最高者+1
- 葉節點的高度為0(或1，視題目要求)
```cpp
void dfs(int x,int father)
{
h[x]=0;
for(int i:edge[x])
{
if(i!=father)
dfs(i,x),h[x]=max(h[x],h[i]+1);
}
}
```
---
## 經典例題
樹例題
- 樹直徑
圖例題
- 遍歷網格圖(水窪問題)
- 網格圖最短路(走迷宮)
- 倒水問題
----
## [樹直徑](https://cses.fi/problemset/task/1131)
求出一棵樹最遠兩點的距離
- 先任選一點作為根，將其視作有根樹
- 考慮分治法：直徑可能
1. 經過根節點，也就是前兩高度
2. 不經過根節點，也就是在某棵子樹上，因此遞迴計算子樹的答案再取max
- 兩者再取max即為答案
----
```cpp
int ans;
int dfs(int x,int father){
int mh1=0,mh2=0,cur;
for(int i:edge[x]){
if(i!=father){
cur=dfs(i,x);
if(cur>mh1)
mh2=mh1,mh1=cur;
else if(cur>mh2)
mh2=cur;
}
}
ans=max(ans,mh1+mh2);
return mh1+1;
}
```
----
#### 另解
1. 任選一點開始做 DFS，找出最遠(深)的點，記為 mx
2. 從 mx 開始做 DFS，其與最遠點的距離即為直徑(也就是第二次DFS的高度+1)
----
```cpp
int md,mx;
void dfs(int x,int father,int d=0){
if(d>md) md=d,mx=x;
for(int i:edge[x]){
if(i!=father)
dfs(i,x,d+1);
}
}
int find_diameter(){
md=-1;
dfs(0,0);
md=-1;
dfs(mx,mx);
return md;
}
```
----
## [水窪問題](https://zerojudge.tw/ShowProblem?problemid=f493)
給定 $n\times m$ 大小的矩陣，0 代表沒有水，1 代表有水，
問有多少個水窪。
ex
```cpp
3 4
0 0 0 0
1 0 1 1
1 0 1 0
ans : 2
```
----
## 解法
每次遇到水就把那攤水跑過一次全部消除，消除完就可以獲得數量以及每次都更新最大最小值即可
----
## [走迷宮問題](https://zerojudge.tw/ShowProblem?problemid=a982)
給定一個 $n\times n$ 的二維整數數組，用來表示一個迷宮，數組中只包含 $0$ 或 $1$，其中 $0$ 表示可以走的路，$1$ 表示不可通過的牆壁。
最初，有一個人位於左上角 $(1,1)$ 處，已知該人每次可以向上、下、左、右任意一個方向移動一個位置。
請問，該人從左上角移動至右下角 $(n,n)$ 處，至少需要移動多少次。
----
## 解法
由於每次轉移都是從上下左右移動過來的，所以只需要從起點開始將可到達的地方全部塞進去，另外開一個陣列紀錄起點到他的最短距離，每次更新最短距離就好，同時也可以利用最短距離去優化。
----
## [倒水問題](https://vjudge.net/problem/UVA-10603)
給容量分別為 $a,b,c$ 的三杯水，倒法是一杯水到另一杯水倒到自己空或是別人滿為止，一開始 $a,b$是空的 $c$ 是滿的問是否能得到d的水如果不能則輸出 $d'$ (小於 $d$ 最大的容量)
sample :
```cpp
input
2
1 3 6 4
1 12 15 7
output
3 4
14 7
```
----
## 解法
考慮每一個狀態，由於可以枚舉每個狀態
假設最大容量為(6,3,1),而初始狀態為(6,0,0)
{"metaMigratedAt":"2023-06-17T19:03:23.837Z","metaMigratedFrom":"YAML","title":"圖論","breaks":true,"contributors":"[{\"id\":\"e4a3af8b-860c-46a0-96f1-558667fdcf41\",\"add\":20534,\"del\":14007},{\"id\":\"19f09ccf-6b99-452f-971f-955cfc1657f3\",\"add\":97,\"del\":921},{\"id\":\"5df14ba0-4dd2-4172-b309-8b5af9ede7a1\",\"add\":13,\"del\":0}]"}