【刷题】图论——最小生成树：Prim、Kruskal【模板】

假设有n个点m条边。
Prim适用于邻接矩阵存的稠密图，时间复杂度是$O(n^2)$，可用堆优化成$O(nlogn)$。
Kruskal适用于稀疏图，n个点m条边，时间复杂度是$mlog(m)$。

Prim：遍历n次，每次选择连通块和外面的点到连通块距离最短的一条边，并将该边对应点加入连通块中，更新其他店到连通块的距离
Kruskal：将所有边权从小到大排序，依次枚举每条边（a和b相连，边权w），如果发现目前a和b不在一个连通块内，将a和b加入连通块中。

题目

题目链接

Prim

#include <iostream>
#include <cstring>using namespace std;
const int N = 110;
int n;
int w[N][N];
int dist[N]; // 外界每个点和当前连通块直接相连的边的最小值
bool st[N]; // 是否加入连通块int prim() {int res = 0;memset(dist, 0x3f, sizeof(dist));dist[1] = 0;for (int i = 0; i < n; i ++ ) {int t = -1; // 不在连通块内的点里面，距离最小的点for (int j = 1; j <= n; j ++ ) {if (!st[j] && (t == -1 || dist[t] > dist[j])) { // j不在连通块里且或j距离更小t = j;}}res += dist[t];st[t] = true;for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], w[t][j]); // 更新所有t能到的距离}return res;
}
int main() {scanf("%d", &n);for (int i = 1; i <= n; i ++ ) {for (int j = 1; j <= n; j ++ ) {scanf("%d", &w[i][j]);}}cout << prim() << endl;
}

Kruskal

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 110;
const int M = 10010;struct Edge {int a, b, w;bool operator< (const Edge &t) const {return w < t.w;}
};Edge e[M];
int p[N];
int n, w, m;int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}
int kruskal() {for (int i = 1; i <= n; i ++ ) p[i] = i;sort(e, e + m);int res = 0;for (int i = 0; i < m; i ++ ) {int a = find(e[i].a);int b = find(e[i].b);if (a != b) {p[a] = b;res += e[i].w;}}return res;
}
int main() {scanf("%d", &n);m = n * n;for (int i = 0; i < n; i ++ ) {for (int j = 0; j < n; j ++ ) {scanf("%d", &w);e[i * n + j] = {i + 1, j + 1, w};}}cout << kruskal() << endl;
}