图论

图的存储

邻接矩阵

条件：用于点数不多的稠密图，例如 $n = 10^3 , m = 10^6$

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
#define N 100

int w[N][N];
int vis[N];
int n,m;
int a,b,c;

void dfs(int u){
    vis[u] = true;
    for(int v= 1; v<=n;v++ ){
        if(w[u][v]){
            cout << u << "," << v << "," << w[u][v];
        }
        if(vis[v]) continue;
        dfs(v);
    }
}

int main(){
    cin >> n >> m;
    for(int i =1 ; i<=m ; i++){
        cin >> a >> b >> c;
        w[a][b] = c;
    }
    dfs(1);
    return 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
#define N 100

struct edge
{
    int u,v,w;
}e[N];
int vis[N];

int n,m;
int a,b,c;

void dfs(int u){
    vis[u] = true;
    for(int i=1;i<=m;i++){  // 注意这里是遍历边
        if(e[i].u == u){
            int v=e[i].v,w=e[i].w;
            cout << u << v <<w;
            if(vis[v]){
                continue;
            }
            dfs(e[i].v);
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i =1 ; i<=m ; i++){
        cin >> a >> b >> c;
        e[i] = {a,b,c};
    }
    dfs(1);
    return 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
#include<bits/stdc++.h>
using namespace std;
#define N 100

int n,m;
int a,b,c;

struct edge
{
    int v,w;
};
vector<edge> e[N];

void dfs(int u,int fa){
    for(auto ed:e[u]){
        int v = ed.v,w =ed.w;
        if(v == fa) continue;
        cout << u << v << w;
        dfs(v,u);
    }
}

int main(){
    cin >> n >> m;
    for(int i =1 ; i<=m ; i++){
        cin >> a >> b >> c;
        e[a].push_back({b,c});
        e[b].push_back({a,c});
    }
    dfs(1,0);
    return 0;
}

Dijkstra 算法

这个算法如果是 $n = 10^3 m = 10^6$

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
#define N 100
#define inf 0x3f3f3f3f

int n,m;
int a,b,c;
int d[N],vis[N];

struct edge
{
    int v,w;
};
vector<edge> e[N];

void dijkstra(int s){
    for(int i = 0 ; i<=n ;i++) d[i] = inf;
    d[s] = 0;
    for(int i = 1 ; i<n ;i++){  // 枚举次数
        int u = 0;
        for(int j=1;j<=n;j++){
            if(!vis[j] && d[j]<d[u]) u= j;  // 选一个最近的点
        }
        vis[u] = 1;
        for(auto ed:e[u]){
            int v = ed.v,w = ed.w;
            if(d[v]>d[u]+w){
                d[v] = d[u] + w;
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i =1 ; i<=m ; i++){
        cin >> a >> b >> c;
        e[a].push_back({b,c});
    }
    return 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
#define N 100
#define inf 0x3f3f3f3f

int n,m;
int a,b,c;
int d[N],vis[N];

struct edge
{
    int v,w;
};

vector<edge> e[N];
priority_queue<pair<int,int>> q;

void dijkstra(int s){
    for(int i = 0 ; i <=n ; i++){
        d[i] = inf;
    }
    d[s] = 0; q.push({0,s});
    while (q.size())
    {
        auto t = q.top(); q.pop();
        int u = t.second;
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto ed:e[u]){
            int v = ed.v, w = ed.w;
            if(d[v]>d[u]+w){
                d[v] = d[w] + w;
                q.push({-d[v],v});
            }
        }
    }
    
}

Floyd

1
2
3
4
5
6
7
for(int k=1;k<=n;k++){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            p[i][j] = max(p[i][j],p[i][k]+p[k][j]);
        }
    }
}

bellmanford

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
#define N 100
#define inf 0x3f3f3f3f

int n,m;
int a,b,c;
int d[N];

struct edge
{
    int v,w;
};
vector<edge> e[N];

bool bellmanford(int s){
    memset(d,inf,sizeof d);
    d[s] = 0;
    bool flag; // 是否松弛
    for(int i = 1 ; i<= n ;i++){   // 进行 n-1 次才对吧,原来还要加上最后一次检查
        flag = false;
        for(int u = 1 ; u<=n ;u++){
            if(d[u] == inf) continue;  // 减枝
            for(auto ed:e[u]){
                int v = ed.v,w = ed.w;
                if(d[v] > d[u] + w){
                    d[v] = d[u] + w;
                    flag = true;
                }
            }
        }
        if(!flag)  break;
    }
    return flag;  
}

int main(){
    cin >> n >> m;
    for(int i =1 ; i<=m ; i++){
        cin >> a >> b >> c;
        e[a].push_back({b,c});
    }
    return 0;
}

如何优化，只有本轮被更新的点，其出边才可能下一次松弛，可以用队列来维护被跟新的点的集合

拓扑排序

可以判断是否存在环

Kahn算法

算法核心就是用队列维护一个入度为 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
#include<bits/stdc++.h>
using namespace std;

const int N =100;
int n,m;

vector<int> e[N],tp;
int din[N];

bool toposort(){
    queue<int> q;
    for(int i = 1 ; i<= n ;i++){
        if(din[i] == 0) q.push(i);
    }
    while (q.size())
    {
        int x = q.front();
        q.pop();
        tp.push_back(x);
        for(auto y:e[x]){
            if(--din[y] == 0) q.push(y);
        }
    }
    return tp.size() == n;
    
}

int main(){
    cin >> n >> m;
    int a,b;
    for(int i = 0 ; i<m;i++){
        cin >> a >> b;
        e[a].push_back(b);
        din[b]++;
    }
    if(!toposort()) puts("-1");
    else for(auto x:tp) cout << x << " ";
    return 0;
}

还可以用深度搜索来做
【D01 拓扑排序】https://www.bilibili.com/video/BV17g41197sa?vd_source=fd97567c320e2e7e7ae66001b2adf816

leecode 2368

image-20240302121518264

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
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
        vector<int> judge(n);
        for (auto x: restricted) {
            judge[x] = 1;
        }
        // 建立邻接表
        vector<vector<int>> g(n);
        for (auto& v : edges) {
            g[v[0]].push_back(v[1]);
            g[v[1]].push_back(v[0]);
        }

        int cnt = 0;
        function<void(int, int)> dfs = [&](int x, int f) {
            cnt++;
            for (auto& y : g[x]) {
                if (y != f && judge[y] != 1) {
                    dfs(y, x);
                }
            }
            };

        dfs(0, -1);
        return cnt;
    }
};

最短路径打印

image-20240311144201789

如果是简单方法就用结构体里面装一个 string，然后每次都更新一下

image-20240311145007561

image-20240311145016763

另外一个方法就是用一个数组记录前驱

char pre[N][N]

注意打印
image-20240311145232204

image-20240311145432126

最大权重的最小值

image-20240412210042679

与它相邻的一个点的此值和他们之间的边权值取一个max，然后在所有max中取一个min！

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
#include <bits/stdc++.h>
using namespace std;

const int N = 10005;

int n,m,s,t;
vector<pair<int,int>> edge[N];
int dis[N],vis[N];

void bfs(){
	for(int i=1;i<=n;i++){
		dis[i] = N+10;
	}
	dis[s] = 0;
	priority_queue<pair<int,int>> q;
	q.push({0,s});
	while(q.size()){
		int d = -q.top().first,e=q.top().second;
		q.pop();
		if(vis[e]) continue;
		vis[e] = 1;
		for(int i=0;i<edge[e].size();i++){
			pair<int,int> p = edge[e][i];
			int toe = p.first,w = p.second;
			int k = max(dis[e],w);
			if(k<dis[toe]){
				dis[toe] = k;
				q.push({-k,toe});
			}
		}
	}
}

int main(){
	cin >> n >> m >> s >> t;
	int a,b,c;
	for(int i=1;i<=m;i++){
		cin >> a >> b >> c;
		edge[a].push_back({b,c});
		edge[b].push_back({a,c});
	}
	bfs();
	cout << dis[t];
	return 0;
}

kruskal算法

image-20240412211514729

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
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
const int N1 = 5005;
const int N2 = 2e5+1;

int f[N1];
int n,m;

struct Edge{
	int u,v,w;
}edge[N2];

bool cmp(Edge a,Edge b){
	return a.w < b.w ;
}

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

int find(int x){
	if(f[x] == x ) return x;
	f[x] = find(f[x]);
	return f[x];
}

void unio(int x,int y)
{
	int xx = find(x),yy = find(y);
	if(xx == yy) return;
	f[yy] = xx;
	return;  // y合到x 
}
void dis(){
	ini();
	sort(&edge[1],&edge[1]+m,cmp);
	int cnt = 0;
	int ans = 0;
	for(int i=1;i<=m;i++){
		if(cnt==(n-1)) break;
		int f1 = find(edge[i].u);
		int f2 = find(edge[i].v);
		if(f1==f2) {
			continue;
		}else{
			cnt++;
			unio(f1,f2);
			ans += edge[i].w ;
		}
	}
	if(cnt == n-1) cout << ans;
	else{
		cout << "orz";
	}
}

int main(){
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		cin >> edge[i].u >> edge[i].v >> edge[i].w ;
	}
	dis();
	return 0;
}