kruskal
typedef struct s {
int a, b;
int weight;
}Edge;
void kruskal(Graph G, Edge* e, int* parent) {
sort(e); //按边的权值进行排序
init(parent); //初始化并查集
for (int i = 0; i < G.num; i++) {
int a_root = find(parent, e[i].a);
int b_root = find(parent, e[i].b);
if (a_root != b_root) unite(parent, a_root, b_root); //若a,b没在一个集合,则进行合并
}
}
prim
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105, inf = 1 << 30;
int map[maxn][maxn];
int visit[maxn]; //
int d[maxn]; //当前到已选节点到未选节点的最小距离
int prim() {
int ans = 0;
for(int i = 0; i < maxn; i++) {
visit[i] = 0;
d[maxn] = inf;
}
d[1] = 0;
visit[1] = 1;
while (1) {
int v = -1;
for (int i = 1; i <= n; i++) {
if (!visit[i] && (v == -1 || d[i] < d[v])) v = i; //
}
if (v == -1) break; //访问完了,退出
visit[v] = 1;
if (d[v] == inf) return -1; //孤立节点
ans += d[v];
for (int i = 1; i <= n; i++) {
if (!visit[i]) d[i] = min(d[i], map[v][i]);
}
}
return ans;
}