# 110 選手班 - 圖論
###### tags: `宜中資訊` `CP`
Ccucumber12
2021.08.10
---
## Outline
- Topological Sort
- Minimum Spanning Tree
- Shortest Path
- DFS Tree
---
## Topological Sort
----
### Problem
- Given a directed graph $G$
- Find an order of vertices S.T.
- $\forall Edge(u,v)$, $u$ is before $v$
----
### DAG
- Directed Acyclic Graph 有向無環圖
- Topological Sort $\Leftrightarrow$ DAG
- DP
----
### Kahn Algorithm
- let $S$ be set of vertices with $indegree = 0$
- Take any vertex $u$ in $S$:
- put into $L$
- remove all edges from $u$: $(u,v_1)$ $(u,v_2)$...
- add $v$ into $S$ if $indegree = 0$
- repeat until $S$ is empty
- return $L$
----
- Degree: Number of Edges $x$ have
- Indegree: Number of Edges going **in** $x$
- Outdegree: Number of Edges going **out** $x$
----
#### Time Complexity
- Initialize: $O(E+V)$
- Repeat Set: $O(E+V)$
- Total: $O(E + V)$
----
#### Implementation
```c=
#include <bits/stdc++.h>
using namespace std;
vector<int> g[100010] ;
int ind[100010] ;
int main() {
int n, m ;
// input
for(int i=1; i<=n; ++i) {
for(auto j:g[i])
ind[j]++ ;
}
queue<int> q ;
for(int i=1; i<=n; ++i)
if(ind[i] == 0)
q.push(i) ;
vector<int> ans ;
while(q.size() != 0) {
int u = q.front() ;
q.pop() ;
ans.push_back(u) ;
for(auto i:g[u]) {
ind[i]-- ;
if(ind[i] == 0)
q.push(i) ;
}
}
if(ans.size() < n) cout << "Failed" << endl ;
else {
for(auto i:ans) cout << i << ' ' ;
cout << endl ;
}
}
```
----
### DFS
- DFS at any vertex
- If find DAG: Push into $L$
- If find cycle: Return False
- Repeat until every vertex is visited
- Return (Reverse $L$)
----
### vis[x]
- Status
- 0: unvisited
- 1: visiting (in stack)
- 2: visit finished (returned)
- If visit a vertex with $vis[x] = 1$
- $\implies$ cylcle
----
#### Time Complexity
- DFS $O(V+E)$
----
#### Implementation
```c=
#include <bits/stdc++.h>
using namespace std;
vector<int> g[100010] ;
vector<int> ans ;
int vis[100010] ; // 0, 1, 2
bool flag = true ;
void dfs(int x) {
vis[x] = 1 ;
for(auto i:g[x]) {
if(vis[i] == 0)
dfs(i) ;
if(vis[i] == 1)
flag = false ;
if(vis[i] == 2)
continue ;
}
ans.push_back(x) ;
vis[x] = 2 ;
}
int main() {
int n, m ;
// input
for(int i=1; i<=n; ++i)
if(vis[i] == 0)
dfs(i) ;
reverse(ans.begin(), ans.end()) ;
if(flag == true) {
for(auto i:ans) cout << i << ' ' ;
cout << endl ;
} else {
cout << "Failed" << endl ;
}
}
```
---
## Minimum Spanning Tree
----
### Problem
- Given a graph $G$
- Find $V-1$ edges $E$ S.T.
- Forms a Tree in $G$
- $\sum\limits_{e\in E}e_w$ is minimized
----
### Kruskal
- graph $G$ with edges $E$
- Sort $E$ into nondecreasing order by weight
- For each $(u,v,w)$ in $E$
- If $u$, $v$ is not connected:
- add $(u,v,w)$ into $result$
- connect $u$, $v$
- return $result$
----
- maintain a forest of current selection
- if the new edge isn't connected:
- choose it
- connect the two trees
- choose edge by weight in nondecreasing order
----
- Check if $u$, $v$ is in same set
- Unite $set_u$ and $set_v$
- $\implies$ DSU
----
#### Proof
- For a moment, we have chosen edge set $F$
- Consider next edge $e(u,v,w)$
- If $u$, $v$ is not connected and we don't choose it
- $u$, $v$ will be connected by another $e'$ which $e'_w$ > $e_w$
- add $e$ in the final MST will form a cycle where we can replace $e$ with $e'$ and get a smaller MST
- Thus we have to choose $e$
----
#### Time Complexity
- Sort: $O(ElogE)$
- DSU: $O(E\alpha(V))$
- Total: $O(ElogE)$
----
#### Implementation
```c=
#include <bits/stdc++.h>
using namespace std;
struct info {
int a, b, w ;
};
bool cmp(info a, info b) {
return a.w < b.w ;
}
int dsu[100010] ;
void init(int n) {
for(int i=1; i<=n; ++i)
dsu[i] = i ;
}
int find(int x) {
return x == dsu[x] ? x : dsu[x] = find(dsu[x]) ;
}
void unite(int x, int y) {
dsu[find(x)] = find(y) ;
}
int main() {
int n, m ;
cin >> n >> m ;
vector<info> v(m) ;
for(int i=0; i<m; ++i) {
cin >> v[i].a >> v[i].b >> v[i].w ;
}
sort(v.begin(), v.end(), cmp) ;
init(n) ;
int ans = 0 ;
for(auto i:v) {
if(find(i.a) != find(i.b)) {
unite(i.a, i.b) ;
ans += i.w ;
}
}
cout << ans << endl ;
}
```
----
### Prim
- Set any vertex as root
- Find the smallest adjacent edge and add to the result
- Repeat until all the vertices are in result
----
#### Heap
- Find the smallest edge in set
- add edges into set
- $\implies$ priority_queue
----
#### Time Complexity
- Find smallest edge: $O(ElogE)$
- add edge into pq: $O(ElogE)$
- Total: $O(ElogE)$
- Fibonacci Heap: $O(VlogV + E)$
----
#### Implementation
```c=
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> g[100010] ;
int main() {
int n, m ;
cin >> n >> m ;
for(int i=0; i<m; ++i) {
int a, b, w ;
cin >> a >> b >> w ;
g[a].push_back(make_pair(b,w)) ;
g[b].push_back(make_pair(a,w)) ;
}
priority_queue<pair<int,int>> pq ;// <-w, b>
for(auto i:g[1]) {
pq.push(make_pair(-i.second, i.first)) ;
}
int vis[100010] = {}, ans = 0;
vis[1] = true ;
while(pq.size() != 0) {
auto u = pq.top() ;
pq.pop() ;
if(vis[u.second]) continue ;
vis[u.second] = true ;
ans -= u.first ;
for(auto i:g[u.second]) // i: <b, w>
if(!vis[i.first])
pq.push(make_pair(-i.second, i.first)) ;
}
cout << ans << endl ;
}
```
---
## Shortest Path
----
### Problem
- Given a weighted graph $G$
- Find a path from $S$ to $T$ S.T.
- The sum of weight is minimized
- Type:
- Single Source
- All pairs
----
### Floyd-Warshall
- All pairs shortest path
- Easy to code
- Find smallest cycle
----
#### Relax
- 鬆弛
- $\delta(s,t) = min(\delta(s,t),\ \delta(s,i)+\delta(i,t))$
----
#### DP
- Let $D_{i,j,k}$ be shortest path from $i$ to $j$ using first $k$ points to relax
- if pass $k$: $D_{i,j,k} = D_{i,k,k-1} + D_{k,j,k-1}$
- if not pass $k$: $D_{i,j,k} = D_{i,j,k-1}$
- $\implies$ $D_{i,j,k}=min(D_{i,j,k-1}, D_{i,k,k-1} + D_{k,j,k-1})$
----
- $dp[i][j][k] = min(dp[i][j][k-1], dp[i][k][k-1], dp[k][j][k-1])$
- $dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])$
----
#### Time Complexity
- $O(V^3)$
- small constant
----
#### Implementaion
```c=
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f3f ;
int dp[110][110] ;
int main() {
int n, m ;
cin >> n >> m ;
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
dp[i][j] = INF ;
for(int i=1; i<=n; ++i)
dp[i][i] = 0 ;
for(int i=0; i<m; ++i) {
int a, b, w ;
cin >> a >> b >> w ;
dp[a][b] = min(dp[a][b], w) ;
}
for(int k=1; k<=n; ++k)
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]) ;
// cout << dp[s][t] << endl ;
}
```
----
### Bellman-Ford
- Single source shortest path
- Support negative edge
- Find Negative cycle
----
#### Relax
- let $dist(u)$ be shortest path from $S$ to $u$
- $relax(u,v)$: $dist(u) = min(dist(u), dist(v) + len(v,u)$
----
- For each edge $(u,v) \rightarrow relax(u,v)$
- Repeat until can't relax any $dist(u)$
----
#### Time Complexity
- At most relax $V-1$ times
- every time at least find one shortest path
- at most $V-1$ shortest path
- $O(VE)$
----
#### Negative Cycle
- Relax successfully at the $V$ time
- $\implies$ negative cycle
----
#### Implementation
```c=
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f ;
struct info {
int a, b, w ;
};
int main() {
int n, m, s ;
cin >> n >> m >> s ;
vector<info> v(m) ;
for(int i=0; i<m; ++i) {
cin >> v[i].a >> v[i].b >> v[i].w ;
}
vector<int> d(n + 1, INF) ;
d[s] = 0 ;
bool flag ;
for(int i=1; i<=n; ++i) {
flag = false ;
for(auto j:v) {
if(d[j.a] + j.w < d[j.b]) {
d[j.b] = d[j.a] + j.w ;
flag = true ;
}
if(d[j.b] + j.w < d[j.a]) {
d[j.a] = d[j.b] + j.w ;
flag = true ;
}
}
if(flag == false) break ;
else if(i == n) {
cout << "negative cycle" << endl;
return 0;
}
}
for(int i=1; i<=n; ++i) cout << d[i] << ' ' ;
cout << endl ;
}
```
----
#### SPFA
- only the adjacent edges need to relax
- $\implies$ queue
- $O(E) \sim O(VE)$
----
### Dijkstra
- Single source shortest path
- Only non-negative edge
- Best Time complexity
----
- let $S$ be current shortest path set
- Relax all the edges using $S$
- Find the smallest new vertex and put into $S$
- Repeat until all the vertices are in $S$
----
#### Heap
- Find the smallest vertex in set
- add relaxed vertex in set
- $\implies$ priority_queue
----
#### Proof
- DP
- If don't select the smallest vertex
- The other path going to $x$ will only be larger
----
#### Time Complexity
- Find smallest: $O(ElogE)$
- insert vertex: $O(ElogE)$
- Total: $O(ElogE)$
----
#### Implementation
```c=
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> g[100010] ; // <b, w>
const int INF = 0x3f3f3f3f ;
int main() {
int n, m, s ;
cin >> n >> m >> s ;
for(int i=0; i<m; ++i) {
int a, b, w ;
cin >> a >> b >> w ;
g[a].push_back(make_pair(b, w)) ;
g[b].push_back(make_pair(a, w)) ;
}
priority_queue<pair<int,int>> pq; // <-dist[i], i>
vector<int> dist(n + 1, INF) ;
dist[s] = 0 ;
for(auto i:g[s]) { // <b, w>
pq.push(make_pair(-(dist[s] + i.second), i.first)) ;
}
while(pq.size() != 0) {
auto u = pq.top() ; // <-dist[i], i>
pq.pop() ;
if(dist[u.second] != INF) continue ;
dist[u.second] = -u.first ;
for(auto i:g[u.second]) { // <b, w>
if(dist[i.first] == INF)
pq.push(make_pair(-(dist[u.second] + i.second), i.first)) ;
}
}
for(int i=1; i<=n; ++i) cout << dist[i] << ' ' ;
cout << endl ;
}
```
----
### Compare
| | Floyd-Warshall | Bellman-Ford | Dijkstra |
| -------- | -------------- | ------------------- | ------------- |
| Time | $O(V^3)$ | $O(VE)$ | $O(ElogE)$ |
| Problem | All Pairs | Single Source Cycle | Single Source |
| Negative | O | O | X |
| Usage | Smallest cycle | Negative cycle | |
---
## Credit
- 演算法筆記
- OI wiki
- https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/
- https://codeforces.com/blog/entry/68138
{"metaMigratedAt":"2023-06-16T06:40:38.789Z","metaMigratedFrom":"Content","title":"110 選手班 - 圖論","breaks":true,"contributors":"[{\"id\":\"45262441-89e4-46ca-959b-c0d6fadb64e2\",\"add\":11981,\"del\":887}]"}