owned this note
owned this note
Published
Linked with GitHub
從零開始學圖論
==
###### tags: `C++`
## Graph
圖,由點與邊組成。
## 圖的種類
1. 無向圖:可以從 u 走到 v 也能走回來。
2. 有向圖:這條邊允許從 u 走 到 v,但不能往回走。
## Tree
擁有以下特徵之一的稱為樹(Tree)
1. 連通 且 V = E + 1。 (點、邊)
3. 兩點間存在唯一的簡單路徑。 (意即不可刪任意條路徑)
3. 沒有環,但加上任意一條邊就有環。
4. 若節點編號存在順序,除了根,每個節點都伸出一條邊連到父節點。
## 相關名詞
1. 根 : 最上層的點
2. 節點 : 储存的每筆資料
3. 葉 : 最下層的點
4. 父節點 : 現在節點上方直連點
5. 子節點 : 現在節點下方連結的點
6. 祖先 : 父節點之上的點,意旨向下dfs可以找到現在節點
### 存樹
以下介紹後面會使用的方法
主要是記下兩點關係,
像是 a 跟 b 相連,就讓 a 的陣列中存入 b。
利用動態陣列(vector)的特性,
只須不斷把點兩點的關係丟入。
當然也可以選擇開struct。
```cpp=
vector<int>tree[1024];
int main()
{
int n, a, b;
cin >> n;
while(n--)
{
cin >> a >> b;
tree[a].emplace(b);
tree[b].emplace(a);
}
}
```
### 遍歷樹---DFS
走一點,走到不能再走為止。
再來會回到上一點,重複動作。
以遞迴執行。
```cpp=
vector<int>tree[1024];
bool vis[100005]; //紀錄是否走過以避免重複走造成的無限迴圈
void dfs(int x)
{
vis[x] = 1;
for(int i : tree[x].first)
{
if(!vis[i])
dfs(i);
}
}
```
## 遍歷---BFS
走完所有子節點,同時將該點的子節點存入queue,不斷循環。
```cpp=
vector<int>vec[100005];
queue <int>que;
bool vis[100005];
void bfs(int x)
{
vis[x] = 1;
que.emplace(x);
while(!que.empty)
{
int front = que.front();
que.pop();
for(int i : vec[front]) //走完所有子節點
{
if(!vis[i]) //避免鬼打牆
{
vis[i] = 1,
que.emplace(i);
}
}
}
}
```
## 紀錄父節點
方法是由dfs、bfs遍歷時,直接記錄下來。
下方提供dfs版
```cpp=
vector<int>vec[1024];
bool visable[1024];
int parent[1024];
void dfs(int x)
{
visable[x] = 1;
for(int i:visable[x])
{
if(!visable[i])
{
visable[i] = 1;
parent[vis[i]] = x;
}
}
}
```
## 某點最遠點
用 dfs 特性看深度,不斷刷新最遠值。
```cpp=
vector<pair<int, int> >vec[1024];
bool vis[1024];
pair<int, int>far;
void dfs(int x, int dis, int ord)
{
vis[x] = 1;
for(pair<int, int> i:vec[x])
{
if(!vis[i.first])
{
vis[i.first] = 1;
if (dis + i.second > far.second) //刷新最遠點
{
far.first = x,
far.second = dis;
}
dfs(i.first, dis + i.second);
}
}
}
```
:::info
權重為邊的長度
:::
## 樹直徑
先找任一點的最遠點,該點的最遠點與該點將會組成樹的直徑,
也就是相離最遠的兩點。
[題源TOJ 378](https://toj.tfcis.org/oj/pro/378/)
```cpp=
vector<pair<int, int> > node[100005];
pair<int, int> far[2];
bool vis[100005];
int ord; //相當於index
void dfs(int x, int dis)
{
vis[x] = 1;
for(pair<int, int> cld:node[x])
{
if(!vis[cld.first])
{
vis[cld.first] = 1;
dis += cld.second;
if(dis > far[ord].second)
{
far[ord].first = cld.first;
far[ord].second = dis;
}
dfs(cld.first, dis);
dis -= cld.second;
}
}
}
int main()
{
int m, n;
cin >> m >> n;
while(n--)
{
int a, b, cost;
cin >> a >> b >> cost;
node[a].push_back({b, cost});
node[b].push_back({a, cost});
}
dfs(0, 0);
memset(vis, 0, sizeof(vis));
ord++;
dfs(far[0].first, 0);
memset(vis, 0, sizeof(vis));
cout << far[1].second << "\n";
}
```
## 最短距離演算法
### Dijkstra演算法
主要是 bfs + greedy,只走每層中最近的路。
```cpp=
#define pii pair<int, int>
vector<pii>vec[100005];
priority_queue<pii, vector<pii>, greater<pii> >pq;
int n, m, end, sta, dis[10005];
bool vis[100005];
void djs()
{
while(!pq.empty())
{
int w = pq.top().first,
u = pq.top().second;
pq.pop();
if (dis[u] < w) continue; //如果w已經大於現在距離,則可以省略
for(pii v: vec[u])
{
if(dis[v.second] > w + v.first) //走比較近的路
{
dis[v.second] = w + v.first;
pq.push({dis[v.second], v.second});
}
}
}
}
int main()
{
memset(dis, 0x3f3f3f3f, sizeof(dis));
cin >> n >> m;
for(int i = 0;i < m; i++)
{
int x, y, w; //x -> y 邊權 w
cin >> x >> y >> w;
vec[x].push_back({w, y});
vec[y].push_back({w, x});
}
cin >> sta >> en;
dis[sta] = 0;
pq.push({0 , sta});
djs();
cout << dis[end] << '\n';
}
```
### Bellman-Ford演算法
鬆弛是這個演算法的核心,再加上暴力跑一次找最小邊
```cpp=
vector< pair<int, int> >vec[500005];
int n, m, sta, en, dis[500005];
void bl()
{
for(int k = 0; k < m; k++)
{
for(int i = 0; i < n; i++)
{
for(auto j:vec[i])
{
dis[j.first] = min(dis[j.first], dis[i] + j.second);
}
}
}
}
int main()
{
memset(dis, 1e9+10, sizeof(dis));
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int a, b, w;
cin >> a >> b >> w;
vec[a].push_back({b, w});
vec[b].push_back({a, w});
}
cin >> sta >> en;
dis[sta] = 0;
bl();
cout << dis[en] << '\n';
}
```
### SPFA演算法(Bellman-Ford演算法的改進版本)
```cpp=
#include<bits/stdc++.h>
#include<vector>
#include<queue>
using namespace std;
vector< pair<int, int> >vec[10005];
queue<int> que;
int n, m, sta, en, dis[10005];
bool vis[10005];
void bl()
{
while(!que.empty())
{
int u = que.front();
que.pop();
vis[u] = 0;
for(auto i : vec[u])
{
if(dis[i.first] > dis[u] + i.second)
{
dis[i.first] = dis[u] + i.second;
if (!vis[i.first])
{
que.emplace(i.first);
}
}
}
}
}
int main()
{
memset(dis, 1e9+10, sizeof(dis));
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int a, b, cost;
cin >> a >> b >> cost;
vec[a].push_back({b, cost});
vec[b].push_back({a, cost});
}
cin >> sta >> en;
que.emplace(sta);
dis[sta] = 0;
bl();
cout << dis[en] << '\n';
}
```
### Floyd-Warshall演算法
## 線段樹
```cpp=
#include<iostream>
using namespace std;
long long n, q1, q2, a[2000005], st[8000005];
void bldst(int l, int r, int idx)
{
if(l == r)
{
st[idx] = a[l];
return;
}
int m = (l+r)/2;
bldst(l, m, idx*2);
bldst(m+1, r, idx*2+1);
st[idx] = max(st[idx*2], st[idx*2+1]);
}
void modify(int pos, int val, int l = 1, int r = n, int idx = 1)
{
if(l == r && l == pos)
{
st[idx] = val;
return;
}
int m = (l+r)>>1;
pos <= m ? modify(pos, val, l, m, idx*2) : modify(pos, val, m+1, r, idx*2+1);
st[idx] = max(st[idx*2], st[idx*2+1]);
}
long long query(int pl, int pr, int l = 1, int r = n, int idx = 1)
{
if(pl <= l && pr >= r) return st[idx];
int m =(l+r)/2;
long long res = -(1LL<<62);
if (pl <= m)
{
res = max(res, query(pl, pr, l, m, idx*2));
}
if (pr >= m+1)
{
res = max(res, query(pl, pr, m+1, r, idx*2+1));
}
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
bldst(1, n, 1);
cin >> q1;
for(int i = 1; i <= q1; i++)
{
char c;
long long a, b;
cin >> c >> a >> b;
if(c == 'C') modify(a, b);
else cout << query(min(a, b), max(a, b))/2 << '\n';
}
}
```
### zkw線段樹
```cpp=
```