图算法

本文最后更新于 2024年9月12日 晚上

图算法

基本图算法

1. 广搜(bfs)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<bool> visited;
vector<vector<int>> graph;

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";
        for (int i = 0; i < graph[node].size(); i++) {
            int next = graph[node][i];
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m; // 输入图的节点数和边数
    graph.resize(n);
    visited.resize(n, false);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入边的两个节点
        graph[u].push_back(v);
        graph[v].push_back(u); // 无向图需要加上这一行
    }
    bfs(0); // 从节点0开始广度优先搜索
    return 0;
}

2. 深搜(dfs)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>

using namespace std;

vector<bool> visited;
vector<vector<int>> graph;

void dfs(int node) {
    cout << node << " ";
    visited[node] = true;
    for (int i = 0; i < graph[node].size(); i++) {
        int next = graph[node][i];
        if (!visited[next]) {
            dfs(next);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入图的节点数和边数
    graph.resize(n);
    visited.resize(n, false);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入边的两个节点
        graph[u].push_back(v);
        graph[v].push_back(u); // 无向图需要加上这一行
    }
    dfs(0); // 从节点0开始深度优先搜索
    return 0;
}

3. 拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int indegree[200005];
vector<int>p[400005];
int n,m;
void topological_sort(){
    priority_queue<int> dot;
    for(int i=1;i<=n;i++){
        if(indegree[i]==0){
            dot.push(i);
        }
    }
    
    while(!dot.empty()){
        int v=dot.top();
        dot.pop();
        cout<<v<<" ";
        int size=p[v].size();
        for(int i=0;i<size;i++){
            indegree[p[v][i]]--;
            if(indegree[p[v][i]]==0){
                dot.push(p[v][i]);
            }
        } 
    }
}

最短路径算法

1. dijkstra求单源最短路径

原理是广搜加dp
时间复杂度是$O(mlogm)$
每次使用时记得将dist的元素均置为LLONG_MAX,一般用于带权有向图，且权值无负数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;

vector<vector<pair<int, int>>> graph(n+2);
void addEdge(vector<vector<pair<int, int>>>& graph, int u, int v, int w) {
    graph[u].push_back({v, w});
}
long long dist[305][305];
void dijkstra(vector<vector<pair<int, int>>>& graph, int start) {
    
    dist[start][start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        for (auto edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[start][u] + w < dist[start][v]) {
                dist[start][v] = dist[start][u] + w;
                pq.push({dist[start][v], v});
            }
        }
    }

}

2. Floyd-Warshall算法求所有结点最短路径

时间复杂度为$O(n^3)$

1
2
3
4
5
6
void floyd(){
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
}

状态表示：我们用$d [ k , i , j ]$表示从i走到j，且中间经过的点的编号不超过k的所有路径长度的最小值，什么叫做中间经过点的编号不超过k呢？假设i到j中间经过所有点为$a_1 , a_2 , . . . ,a_m$

​
，那么这m个点的编号值都$<= k$ ，注意不要与总共经过不超过k个点混淆。

状态计算：$d [ k , i , j ]$的计算可以分为两类：

从i走到j，且中间经过的点的编号不超过k且不包含k的所有节点路径：那么它就等价于从i走到j且经过的点的编号不超过k - 1的所有路径的最小值，即$d [ k − 1 , i , j ]$

从i走到j，且中间经过的点的编号不超过k且包含k的所有节点路径：那么我们就会发现，它一定会从i走到k，并且一定会从k走到j，因此我们可以将它分为两段之和：

从i走到k，且中间经过的点的编号不超过k - 1的所有节点路径的最小值，即$d [ k − 1 , i , k ] $
从k走到j，且中间经过的点的编号不超过k - 1的所有节点路径的最小值，即$d [ k − 1 , k , j ] $
并且前后两段是没有关系的，所以这种情况的表示就是$d [k − 1 ,i, k ] + d [ k − 1 , k , j ] $

因此，我们可以得出$d [ k , i , j ] = m i n ( d [ k − 1 , i , j ] , d [k − 1 , i , k ] + d [ k − 1 , k , j ] ) $

3. 最小生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <algorithm>
#include <iostream>

#define V_MAX 300005
#define E_MAX 500005

using namespace std;
typedef long long ll;

struct Edge {
    int x, y, w;
    bool operator<(const Edge &b) const { return w < b.w; }
} e[E_MAX];

int v[V_MAX];

int Find(int x);
bool isUnion(int x, int y);
void Union(int x, int y); //合并
void makeSet(int n);  //初始化并查集

int main() {
    int n, m;
    cin >> n >> m;
    makeSet(n);
    for (int i = 0; i < m; i++)
        cin >> e[i].x >> e[i].y >> e[i].w;
    sort(e, e + m);
    int cnt = 0;
    ll sum = 0;
    for(int i = 0; cnt < n - 1; i++){
        if(isUnion(e[i].x, e[i].y))
            continue;
        cnt++;
        sum += e[i].w;
        Union(e[i].x, e[i].y);
    }
    cout << sum;
    return 0;
}

void makeSet(int n) {
    for (int i = 1; i <= n; i++)
        v[i] = i;
}

int Find(int x) {
    if (v[x] == x)
        return x;
    return v[x] = Find(v[x]);
}

bool isUnion(int x, int y) { return Find(x) == Find(y); }
void Union(int x, int y) { v[Find(y)] = Find(x); }

流网络问题

1.最大流dinic算法

流网络中的增广路是指：从源节点到汇点的一条路径，并且在这条路径上还存在可以增加流量的余地。这条路径上的残余容量（即路径上各边的剩余容量）都大于 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include<bits/stdc++.h>
using namespace std;
const int N=150;
const int M=5050;
int h[N],idx=1;
int n,m,s,t;//s代表源点，t代表汇点
//数组h存i点的最后一条出边的编号，便于点i的所有出边的遍历,idx图中代表所有出边的编号 
int d[N],cur[N];
//数组d代表图的层数，cur存在dfs时，u当前的出边编号，因为已经遍历过的边不存在新的增广路径 
struct edge{
 int v;//出边的终点 
 long long w;//出边的容量 
 int ne;//1个点的第n条出边存第n-1条出边的编号 
}e[M];
void addedge(int u,int v,int w){
 e[++idx]={v,w,h[u]};
 h[u]=idx;
}
bool bfs(){
 memset(d,0,sizeof d);
 queue<int>q;
 q.push(s);//s代表源点 
 d[s]=1;//源点在第一层 
 while(!q.empty()){
  int u=q.front();q.pop();
    for(int i=h[u];i!=0;i=e[i].ne){
        int v=e[i].v;
        if(d[v]==0&&e[i].w){
            d[v]=d[u]+1; 
            q.push(v);
            if(v==t) return true;//说明找到了从源点到汇点的增广路径 
        }//v如果还没分层，且该出边的剩余容量不为0 
    }
 }
 return false; 
}
long long dfs(int u,long long mf){//mf代表可以从u点流出的剩余流量 
 if(u==t) return mf;//如果已经到达汇点，返回mf；
 long long sum=0;//u点的总流出量的最大值 
    for(int i=cur[u];i!=0;i=e[i].ne){
        cur[u]=i;//记录当前的弧，减少总遍历次数
        int v=e[i].v;
        if(d[v]==d[u]+1&&e[i].w){
            long long f=dfs(v,min(mf,e[i].w));
            e[i].w-=f;
            sum+=f; 
            mf-=f;
            if(mf==0) break;//如果u点没有可以流出的流量了，结束循环 
        }
    } 
    if(sum==0) d[u]=0;//sum=0代表u点无法到达汇点，该点标记为-1层，直接排除循环
    return sum; 
} //dfs的作用是求从u点流出的最大流量值。 
long long dinic(){
    long long flow=0;
        while(bfs()){//如果存在增广路，就继续搜
            memcpy(cur,h,sizeof h);
            flow+=dfs(s,1e13);
        }
    return flow;
}

2.最大二分匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 405;

vector<int> graph[MAXN];
int match[MAXN];
bool visited[MAXN];

//寻找增广路径 
bool dfs(int u) {
    for (int v : graph[u]) {
        if (!visited[v]) {
            visited[v] = true;
            if (match[v] == -1||dfs(match[v])) {
                match[v] = u;//直到找到未饱和点
                return true;
            }
        }
    }
    return false;
}
//最大二分匹配 
int maxMatching(int n) {
    int count = 0;
    memset(match, -1, sizeof(match));//先初始化所有点未匹配 
    for (int i = 0; i < n; i++) {
        memset(visited, false, sizeof(visited));//深搜点标记 
        if (dfs(i)) {
            count++;
        }
    }
    return count;
}