假设 n 表示图中点数，m 表示图中边数。
Prim算法
适用于稠密图，时间复杂度是$O(n^2)$
核心思想：每次挑一条与当前集合相连的最短边
C++代码模板
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
// st[i] 表示点i是否在当前生成树集合中
// dist[i] 表示点i到当前集合的最短边的长度
// g[i][j] 表示点i和点j之间边的长度
// 返回值：最小生成树中所有边的总长度
int Prim(){
int res = 0;
for (int i = 1; i <= n; i ++ ){
dist[i] = INF;
st[i] = false;
}
dist[1] = 0;
for (int i = 1; i <= n; i ++ ){
int id = -1, min_dist = INF;
// 寻找最短边
for (int j = 1; j <= n; j ++ )
if (!st[j] && dist[j] < min_dist){
id = j;
min_dist = dist[j];
}
st[id] = true;
res += dist[id];
// 用新加入的点更新其余点到生成树的最短边
for (int j = 1; j <= n; j ++ )
if (!st[j])
dist[j] = min(dist[j], g[id][j]);
}
return res;
}
Kruskal算法
适用于稀疏图，时间复杂度$O(mlogm)$。
核心思想：从小到大挑不多于的边。
C++代码模板
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
// 边的信息
struct Edge{
int a, b, v;
bool operator< (const Edge &W) const{
return v < W.v;
}
};
// 并查集——寻找当前集合的代表元素
int find(int x){
if (father[x] != x) father[x] = find(father[x]);
return father[x];
}
// 所有边存储在 Edge edges[M];
// 函数返回最小生成树中所有边的总长度
int Kruskal(){
int res = 0;
// 初始化并查集代表元素
for (int i = 1; i <= n; i ++ ) father[i] = i;
sort(edge, edge + m);
for (int i = 0; i < m; i ++ ){
int a = edge[i].a, b = edge[i].b;
if (find(a) != find(b)){
res += edge[i].v;
father[find(a)] = find(b);
}
}
return res;
}
