# 基礎圖論
---
## 圖?
圖論（Graph Theory）是探討關於圖（Graph）這個數學模型的理論。透過研究如何解決 graph 上的各種問題，只要能將題目對應至 graph 這個模型上，就能用 graph 的做法去解這道題目。
有點像尋找萬靈藥的感覺，只要將各種題目想辦法轉到泛用的 graph 模型上，就能通通當作 graph 問題來解。
by [sa](https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FSJoWKFtcm)
----
分享一個畫圖神器
[嘻嘻](https://csacademy.com/app/graph_editor/)
---
## 圖的基本
----
### 點&邊
圖由$點(node)$以及$邊(edge)$構成
```graphviz
graph exp
{
1 -- 1 -- 4 -- 5 -- 1 -- 4;
}
```
```graphviz=
graph exp
{
a -- b -- c -- d -- b;
}
```
```graphviz=
graph exp
{
k -- c -- c -- is -- handsome;
}
```
```graphviz=
graph exp
{
dad -- son;
mom -- son;
}
```
----
### 環
起點與終點相同的一條路徑，且路徑上經過的點不重複
```graphviz
graph
{
rankdir = LR
1 -- 2;
2 -- 3;
1 -- 3;
}
```
這裡有一個環為$1-2-3-1$
----
```graphviz
graph
{
rankdir = LR
1 -- 2;
2 -- 3;
3 -- 4;
2 -- 4;
1 -- 4;
}
```
$1-2-3-4-1$是一個環
$2-3-4-2$也是一個環
$1-2-3-4-2-1$不是一個環
----
### 連通塊
一個圖中的一個子圖，滿足任兩點之間互相連通
```graphviz
graph 連通塊{
subgraph cluster{
1, 3, 4, 6
}
subgraph cluster_a{
2, 5, 7, 8, 9
}
subgraph cluster_c{
a, b, c, d
}
subgraph cluster_t{
10
}
1 -- 3
1 -- 4
3 -- 6[constraint = none]
6 -- 4
2 -- 5 -- 7
2 -- 8
8 --9
a -- b
c -- d
a -- d
10
}
```
這張圖有4個連通塊
圖by tw87
---
## 圖的分類
----
### 有向圖vs.無向圖
```graphviz
digraph exp
{
1 -> 1 -> 4 -> 5;
}
```
```graphviz
graph exp
{
1 -- 1 -- 4 -- 5;
}
```
有向圖為單向道
無向圖為雙向道
----
### 帶權圖 vs. 無權圖
```graphviz=
graph{
9 -- 5 [label = 10];
5 -- 2 [label = 12];
2 -- 7 [label = 77];
}
```
```graphviz=
graph {
9 -- 5 ;
5 -- 2 ;
2 -- 7 ;
}
```
可以把邊權當成經過時需要支付的過路費
也可以把無權圖當做邊權都相同的帶權圖
---
## 存圖
* 鄰接矩陣
* 鄰接串列
----
### 鄰接矩陣
使用$n^{2}$大小的二維陣列儲存一張圖
其中$n$為點的數量
$ary[a][b] = 1$表示可從a走到b
----
```graphviz
graph exp
{
rankdir = LR
1 -- 2 -- 4 -- 5 -- 1 -- 3;
}
```
| \ | 1 | 2 | 3 | 4 | 5 |
| --- | --- | --- | --- | --- | --- |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 2 | 1 | 0 | 0 | 1 | 0 |
| 3 | 1 | 0 | 0 | 0 | 0 |
| 4 | 0 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 0 | 1 | 0 |
----
### 鄰接串列
用$n$個一維陣列儲存每個點與誰相連
通常都是用這個方法存圖
----
```graphviz
graph exp
{
rankdir = LR
1 -- 2 -- 4 -- 5 -- 1 -- 3;
}
```
1 : 2、3、5
2 : 1、4
3 : 1
4 : 2、5
5 : 1、4
----
```cpp
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
v[a].pb(b);
v[b].pb(a);
}
```
----
[TOJ765](https://toj.tfcis.org/oj/pro/765/)
估一下複雜度
---
## 圖的走訪
dfs
bfs
----
### DFS(深度優先搜尋)
----
```graphviz
graph exp
{
1 -- 2 -- 3 -- 4 -- 5;
1 -- 6 -- 7;
6 -- 8
1 -- 10
7 -- 9
}
```
拜訪順序是$1-2-3-4-5-6-7-9-8-10$
----
```cpp
vector<int> edge[maxn];
bool vis[maxn];
void dfs(int id){
vis[id] = true;
for(auto i : edge[id]){
if(!vis[i]) dfs(i);
}
return;
}
```
----
### BFS(廣度優先搜尋)
minecraft水流
跟格子點的BFS很像
----
```graphviz
graph
{
1 -- 2 -- 3 -- 4 -- 5;
1 -- 6 -- 7;
6 -- 8
1 -- 10
7 -- 9
}
```
拜訪順序是$1-2-6-10-3-7-8-4-9-5$
也就是先依序拜訪起點、從起點走一步可以到的點、從起點走兩步可以到的點、從起點走三步可以到的點...
----
```cpp
while(q.size()){
int a = q.front();
q.pop();
if(vis[a]) continue;
vis[a] = true;
for(auto w : v[a]){
if(!vis[w]) q.push(w);
}
}
```
----
格子點BFS
[cses1193](https://cses.fi/problemset/task/1193)
[toj432](https://toj.tfcis.org/oj/pro/432/)
----
[cses1192](https://cses.fi/problemset/task/1192)
[cses1666](https://cses.fi/problemset/task/1666)
[cses1667](https://cses.fi/problemset/task/1667)
[cses1668](https://cses.fi/problemset/task/1668)
[cses1193](https://cses.fi/problemset/task/1193)
[cses1669](https://cses.fi/problemset/task/1669)
[cses1678](https://cses.fi/problemset/task/1678)
---
## 最短路徑問題
* Dijkstra
* Bellman-Ford
* Floyd–Warshall
----
### Dijkstra
換了名字的BFS
----
Dijk經常使用於單源最短路徑問題，但它有使用條件
**邊權必須大於0**
[cses1671](https://cses.fi/problemset/task/1671/)
----
主要概念
將所有還沒算出最短距離的點中，找出距離起點最近的點A，並將其設為最短距離
再更新A能夠經過一條邊抵達的所有點，判斷是否為更短的距離
~~好抽象~~
----
```graphviz
graph
{
rankdir = LR
a -- b [label = 2]
a -- c [label = 8]
a -- d [label = 8]
b -- e [label = 5]
c -- e [label = 6]
e -- f [label = 6]
d -- f [label = 5]
a[color = green]
}
```
將起點的距離設為0，其他點設為$\infty$
| \ | a | b | c | d | e | f |
| -------- | -------- | --- | --- | --- | --- | -------- |
| 距離 | 0 |$\infty$ |$\infty$ | $\infty$ | $\infty$ | $\infty$|
----
```graphviz
graph
{
rankdir = LR
a -- b [label = 2]
a -- c [label = 8]
a -- d [label = 8]
b -- e [label = 5]
c -- e [label = 6]
e -- f [label = 6]
d -- f [label = 5]
a[color = green]
b[color = red]
}
```
b為尚未算出最短距離中離起點最近的點
所以更新b的最短距離
| \ | a | b | c | d | e | f |
| -------- | -------- | --- | --- | --- | --- | -------- |
| 距離 | 0 |2 |$\infty$ | $\infty$ | $\infty$ | $\infty$|
----
```graphviz
graph
{
rankdir = LR
a -- b [label = 2]
a -- c [label = 8]
a -- d [label = 8]
b -- e [label = 5]
c -- e [label = 6]
e -- f [label = 6]
d -- f [label = 5]
a[color = green]
b[color = green]
e[color = red]
}
```
e為尚未算出最短距離中離起點最近的點
所以更新e的最短距離
| \ | a | b | c | d | e | f |
| -------- | -------- | --- | --- | --- | --- | -------- |
| 距離 | 0 |2 |$\infty$ | $\infty$ | 7 | $\infty$|
----
```graphviz
graph
{
rankdir = LR
a -- b [label = 2]
a -- c [label = 8]
a -- d [label = 8]
b -- e [label = 5]
c -- e [label = 6]
e -- f [label = 6]
d -- f [label = 5]
a[color = green]
b[color = green]
e[color = green]
c[color = red]
d[color = red]
}
```
c為尚未算出最短距離中離起點最近的點
所以更新c的最短距離
d也是，先更新哪個都可以
| \ | a | b | c | d | e | f |
| -------- | -------- | --- | --- | --- | --- | -------- |
| 距離 | 0 |2 |8 | 8 | 7 | $\infty$|
----
```graphviz
graph
{
rankdir = LR
a -- b [label = 2]
a -- c [label = 8]
a -- d [label = 8]
b -- e [label = 5]
c -- e [label = 6]
e -- f [label = 6]
d -- f [label = 5]
a[color = green]
b[color = green]
e[color = green]
c[color = green]
d[color = green]
f[color = red]
}
```
f為尚未算出最短距離中離起點最近的點
所以更新f的最短距離
| \ | a | b | c | d | e | f |
| -------- | -------- | --- | --- | --- | --- | -------- |
| 距離 | 0 |2 |8 | 8 | 7 | 13|
----
```graphviz
graph
{
rankdir = LR
a -- b [label = 2]
a -- c [label = 8]
a -- d [label = 8]
b -- e [label = 5]
c -- e [label = 6]
e -- f [label = 6]
d -- f [label = 5]
a[color = green]
b[color = green]
e[color = green]
c[color = green]
d[color = green]
f[color = green]
}
```
結束
| \ | a | b | c | d | e | f |
| -------- | -------- | --- | --- | --- | --- | -------- |
| 距離 | 0 |2 |8 | 8 | 7 | 13|
----
怎麼維護還沒算出最短距離的所有點中，離起點最近的點
----
通常用priority_queue來維護距離起點最近的點
要用set也是可以
```cpp
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);
#define pb push_back
#define F first
#define S second
#define pii pair<long long, int>
vector<pair<int, int>> v[(int)2e5 + 5];
long long dis[(int) 2e5 + 5];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
long long x, y, w;
cin >> x >> y >> w;
v[x].pb({y, w});
}
for(int i = 2; i <= n; i++) dis[i] = 1e15;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push(make_pair(0, 1));
while(q.size()){
auto a = q.top();
q.pop();
if(dis[a.S] < a.F) continue;
for(auto w : v[a.S]){
if(dis[a.S] + w.S < dis[w.F]){
dis[w.F] = dis[a.S] + w.S;
q.push(make_pair(dis[w.F], w.F));
}
}
}
for(int i = 1; i <= n; i++) cout << dis[i] << ' ';
return 0;
}
```
複雜度?
----
$O(mlogm)$
AC!!!
----
### Bellman-Ford
可以處理邊權為負的情況
~~暴力~~
----
反覆檢查每一條邊，看是否能夠更新到起點的距離
如果將對所有邊檢查一次訂為一個回合，那麼經過$N-1$個回合後，就能算出所有點到起點的最短路徑，否則無解
每個回合檢查$E$條邊，最糟情況$N-1$回合
複雜度O(?)
----
如果第$N$回合還能夠更新距離，那麼存在負環
----
```cpp
void bellman_ford(){
for(int i = 1; i <= n; i++){
bool update = false;
for(int j = 1; j <= n; j++)
for(auto k : g[j])
if(dis[k.F] > dis[j] + k.S)
update = true, dis[k.F] = dis[j] + k.S;
if(!update)break;
if(i == n)cout << "neg_cycle" << "\n";
}
}
```
$O(NE)$
----
### Floyd–Warshall
多對多最短路徑
[cses1672](https://cses.fi/problemset/task/1672/)
----
令$dis[k][i][j]$為$i$走到$j$的最短距離，且經過的所有點中，編號均不超過k
```cpp
dis[k][i][j]
=min(dis[k - 1][i][j], dis[k - 1][i][k] + dis[k - 1][k][j])
```
----
令$dis[k][i][j]$為$i$走到$j$的最短距離，且經過的所有點中，編號均不超過k
```cpp
dis[k][i][j]
=min(dis[k - 1][i][j], dis[k - 1][i][k] + dis[k - 1][k][j])
```
其中
$dis[k - 1][i][k] = dis[k][i][k]$
$dis[k - 1][k][j] = dis[k][k][j]$
----
可以把k那維壓掉
```cpp
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
```
```cpp
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
```
$O(N^3)$
---
## DAG
有向無環圖
----
### 入度&出度
點被指向的箭頭數量就是入度
從點指出的箭頭數量就是出度
```graphviz
digraph topological{
{rank = same a b c d e}
b -> e
c -> e
a -> b
a -> c
a -> d
}
```
| | a | b | c | d | e |
| -------- | -------- | --- | --- | --- | -------- |
| 入度 | 0 | 1 | 1|1 | 2|
| 出度 | 3 | 1 | 1| 0 | 0 |
----
### 拓樸排序(Topological sorting)
訂出一個點的序列${v_1, v_2, ... , v_n}$使得$\forall i \le j$
皆不存在$v_j$到$v_i$的路徑
簡單來說就是把點排成一列然後邊不能往前指
```graphviz
digraph topological{
{rank = same 1, 2 3 4 5}
2 -> 5
3 -> 5
1 -> 2
1 -> 3
1 -> 4
}
```
DAG$\iff$有拓樸排序
但拓樸排序不一定只有一種，
上圖2,3,4怎麼交換都是拓樸排序
by tw87
----
如果有一個點，應該擺在它前面的點都已經放進序列中，那麼這個點便可以放進序列形成拓樸排序
----
[cses1679](https://cses.fi/problemset/task/1679/)
```cpp
while(q.size()){
int x = q.front();q.pop();
ans.pb(x);
for(int i : g[x]){
in[i]--;
if(in[i] == 0) q.push(i);
}
}
```
$O(?)$
----
[cses1679](https://cses.fi/problemset/task/1679/)
```cpp
while(q.size()){
int x = q.front();q.pop();
ans.pb(x);
for(int i : g[x]){
in[i]--;
if(in[i] == 0) q.push(i);
}
}
```
$O(N + E)$
----
[cses1681](https://cses.fi/problemset/task/1681/)
[atcoder_dp_g](https://atcoder.jp/contests/dp/tasks/dp_g)
---
## 圖中的特例 ---- 樹
----
一棵 tree 是一個無向的連通圖，具備以下性質：
* 有剛好$N-1$條邊
* 不存在環
* 任兩點間只存在$1$條簡單路徑
可由其一推得其他性質
----
### 簡單路徑
一條路徑中除了起點終點外，所有的點兩兩相異，稱為簡單路徑。
----
### 根(root)
一棵樹不一定要有根，如果題目沒給通常會隨便找一個點當根(通常是0或1)
```graphviz
graph {
1 [color = red]
1 -- 2
1 -- 3
1 -- 4
2 -- 5
2 -- 6
}
```
----
### 葉(leaf)
在樹上度數只有一的節點稱為葉節點
```graphviz
graph {
3, 4 ,5 ,6 [color = red]
1 -- 2
1 -- 3
1 -- 4
2 -- 5
2 -- 6
}
```
----
### 父節點(parent)&子節點 (child)
有根樹中，兩個相鄰的節點，離根較近的節點是另一個節點的父節點，反之為其子節點 (child)
```graphviz
graph {
1 -- 2
1 -- 3
1 -- 4
2 -- 5
2 -- 6
}
```
---
## 樹直徑(Tree Diameter)
----
樹上的任何最長長度的簡單路徑都是此樹的直徑。
----
### 求法
做兩次$DFS$
1. $從任意點開始做 DFS 並找到最遠的那個點x$
1. $接著把 x 當起點再做一次 DFS 找到距離點 x 最遠的點 y$
$如此一來 x與 y 的距離就是樹直徑$
----
[TIOJ1213](https://tioj.ck.tp.edu.tw/problems/1213)
[cses1131](https://cses.fi/problemset/task/1131)
---
## 最小生成樹
(Minimum Spanning Tree)
----
[cses1675](https://cses.fi/problemset/task/1675)
一張圖中，選一些邊把這張圖連通成樹
問最小邊權和
----
### Kruskal
----
對所有邊依權重排序，由小到大只要邊上兩點屬於不同連通塊，就加進去
----
```graphviz
graph {
rankdir = LR
1 -- 2 [label = 3]
2 -- 3 [label = 5]
2 -- 4 [label = 2]
3 -- 4 [label = 8]
5 -- 1 [label = 7]
5 -- 4 [label = 4]
}
```
----
```graphviz
graph {
rankdir = LR
1 -- 2 [label = 3]
2 -- 3 [label = 5]
2 -- 4 [label = 2, color = red]
3 -- 4 [label = 8]
5 -- 1 [label = 7]
5 -- 4 [label = 4]
2[color = red]
4[color = red]
}
```
----
```graphviz
graph {
rankdir = LR
1 -- 2 [label = 3, color = red]
2 -- 3 [label = 5]
2 -- 4 [label = 2, color = green]
3 -- 4 [label = 8]
5 -- 1 [label = 7]
5 -- 4 [label = 4]
2[color = green]
4[color = green]
1[color = red]
}
```
----
```graphviz
graph {
rankdir = LR
1 -- 2 [label = 3, color = green]
2 -- 3 [label = 5]
2 -- 4 [label = 2, color = green]
3 -- 4 [label = 8]
5 -- 1 [label = 7]
5 -- 4 [label = 4, color = red]
2[color = green]
4[color = green]
1[color = green]
5[color = red]
}
```
----
```graphviz
graph {
rankdir = LR
1 -- 2 [label = 3, color = green]
2 -- 3 [label = 5, color = red]
2 -- 4 [label = 2, color = green]
3 -- 4 [label = 8]
5 -- 1 [label = 7]
5 -- 4 [label = 4, color = green]
2[color = green]
4[color = green]
1[color = green]
5[color = green]
3[color = red]
}
```
----
```graphviz
graph {
rankdir = LR
1 -- 2 [label = 3, color = green]
2 -- 3 [label = 5, color = green]
2 -- 4 [label = 2, color = green]
3 -- 4 [label = 8]
5 -- 1 [label = 7, color = red]
5 -- 4 [label = 4, color = green]
2[color = green]
4[color = green]
1[color = green]
5[color = green]
3[color = green]
}
```
編號1跟編號5已經在同一個連通塊
所以這條邊不選
----
```graphviz
graph {
rankdir = LR
1 -- 2 [label = 3, color = green]
2 -- 3 [label = 5, color = green]
2 -- 4 [label = 2, color = green]
3 -- 4 [label = 8, color = red]
5 -- 1 [label = 7]
5 -- 4 [label = 4, color = green]
2[color = green]
4[color = green]
1[color = green]
5[color = green]
3[color = green]
}
```
編號3跟編號4已經在同一個連通塊
所以這條邊不選
----
```graphviz
graph {
rankdir = LR
1 -- 2 [label = 3, color = green]
2 -- 3 [label = 5, color = green]
2 -- 4 [label = 2, color = green]
3 -- 4 [label = 8]
5 -- 1 [label = 7]
5 -- 4 [label = 4, color = green]
2[color = green]
4[color = green]
1[color = green]
5[color = green]
3[color = green]
}
```
綠色部分便是最小生成樹
----
怎麼判斷兩點是否屬於同一連通塊?
----
DSU
複雜度?
----
DSU
$O(mlogm)$
----
```cpp
sort(ary, ary + m, cmp);
for(int i = 0; i < m; i++){
int p = ary[i].a;
int q = ary[i].b;
int x = findroot(p);
int y = findroot(q);
if(x != y){
ans += ary[i].c;
root[x] = y;
}
}
```
點p跟點q之間有一條邊權ary[i].c的邊
----
[kattis-islandhopping](https://open.kattis.com/problems/islandhopping)
---
新年快樂!!!!
{"title":"基礎圖論","description":"圖論（Graph Theory）是探討關於圖（Graph）這個數學模型的理論。透過研究如何解決 graph 上的各種問題，只要能將題目對應至 graph 這個模型上，就能用 graph 的做法去解這道題目。","contributors":"[{\"id\":\"a86f0f85-1d73-4927-861c-8c385cba4545\",\"add\":20871,\"del\":6192}]"}