最小生成树—kruskal和prim算法

发表于 更新于 分类于 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 5 分钟

Kruskal算法模版

  1. 按各边权值进行从小到大排序
  2. 检测是否有环（使用并查集）
    1. 如果两节点属于同一个集合 则说明有环
    2. 如果两节点不属于同一个集合 不成环则进行合并

借助洛谷上的最小生成树

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。
输入格式

第一行包含两个整数 N,MN,M，表示该图共有 NN 个结点和 MM 条无向边。

接下来 MM 行每行包含三个整数 Xi,Yi,ZiXi​,Yi​,Zi​，表示有一条长度为 ZiZi​ 的无向边连接结点 Xi,YiXi​,Yi​。
输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

模版代码如下：

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

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> father;
int ans = 0;
int cnt = 0;

// 构建并查集
void build(int n) {
	for (int i = 0; i <= n; ++i) father.push_back(i);
}
// 查询并查集
int find(int x) {
	if (x != father[x]) father[x] = find(father[x]);
	return father[x];
}
// 合并
void _union(int x, int y, int w) {
	int fx = find(x), fy = find(y);
	if (fx != fy) {
		father[fy] = fx;
		ans += w;
	}
}

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int>> edge;
	for (int i = 0; i < M; ++i) {
		int from, to, weight;
		cin >> from >> to >> weight;
		edge.push_back({ from, to, weight });
	}
	auto cmp = [](vector<int>& a, vector<int>& b) -> bool{
		return a[2] < b[2];
		};
	// 根据权值排序
	sort(edge.begin(), edge.end(), cmp);
	build(N);
	for (auto e : edge) {
		int from = e[0], to = e[1], w = e[2];
		// 如果不成环 则合并
		if (find(from) != find(to)) {
			_union(from, to, w);
			cnt++;
		}
		// 如果成环 则跳过
	}
	if (cnt == N-1) cout << ans;
	else cout << "orz";
	return 0;
}

Prim算法模版

prim算法和Dijkstra算法十分类似

过程如下：

  1. 创建visited数组 初始设为false 即vector<bool>visited(n, false);
  2. 任取一个点 将这个点的所有边加入到小根堆中
  3. 当小根堆不为空 则弹出元素
    1. 弹出元素若已访问过 则continue
    2. 弹出元素若未访问过 则visited[cur] = true; 这里可以计算最小生成树的权值 如ans += weight
    3. 处理各边 将各边加入到堆中
  4. 当小根堆为空 也就得到了最小生成树

针对洛谷上的模版题（见前文）也可以使用prim算法进行计算

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <limits.h>
#include <queue>

using namespace std;

int main() {
    // 建图
    int N, M;
    cin >> N >> M;
    vector<vector<vector<int>>> graph(N + 1);
    for (int i = 0; i < M; ++i) {
        int from, to, weight;
        cin >> from >> to >> weight;
        graph[from].push_back({ to, weight });
        graph[to].push_back({ from, weight });
    }

    // 开始 Prim 算法
    vector<bool> visited(N + 1, false);
    int ans = 0, cnt = 1;

    auto cmp = [](vector<int>& a, vector<int>& b)-> bool {
        return a[1] > b[1]; // 使用小根堆
        };
    priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> q(cmp);
    for (auto i : graph[1]) q.push(i);
    visited[1] = true;

    while (!q.empty()) {
        vector<int> cur = q.top();
        q.pop();
        int from = cur[0], weight = cur[1];

        if (visited[from]) continue;
        visited[from] = true;
        ans += weight; // 累加当前边的权重
        cnt++;

        // 处理各边
        for (auto neighbor : graph[from]) {
            q.push(neighbor);
        }
    }

    // 检查是否所有节点都被访问
    if (cnt == N) {
        cout << ans;
    }
    else {
        cout << "orz";
    }

    return 0;
}

时空复杂度分析

kruskal算法：

  • 时间复杂度 O(E * log E)
  • 空间复杂度 O(V)

prim算法

  • 时间复杂度 O(E * log V)
  • 空间复杂度 O(V)