最小生成树问题
常用的最小生成树一般是无向图。
一般不对边的负权作要求。
一、普里姆算法（Prim算法）
普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
1. 朴素版Prim算法
适用情况：稠密图
时间复杂度：O(n^2^)
思路
- 初始化距离（INF）
- 迭代 n 次
- 找到不在连通块中的距离最小的点
- 用这个点更新其他点到连通块（注意与迪杰斯特拉算法的区别）的距离
- 加入连通块
详解
见代码注释
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;
int n, m;
int g[N][N]; // 稠密图用邻接矩阵存储
int dist[N]; // 每个点到连通块的距离
bool st[N]; // 这个点是否在连通块内
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 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]))
t = j;
// 图不连通，没有最小生成树
if (i && dist[t] == INF)
return INF;
if (i) // 如果不是第一个点
res += dist[t]; // 结果中加入边
// 更新距离
for (int j = 1 ; j <= n ; ++j)
dist[j] = min(dist[j], g[t][j]);
// 加入连通块
st[t] = true;
}
return res;
}
int main()
{
// 初始化距离为正无穷
memset(g, 0x3f, sizeof g);
// 输入
scanf("%d %d", &n, &m);
int a, b, c;
while (m--)
{
scanf("%d %d %d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
// Prim算法
int t = prim();
// 输出
if (t == INF)
printf("impossible\n");
else
printf("%d\n", t);
return 0;
}
2. 堆优化Prim算法【不常用】
适用情况：稀疏图（不如下一个常用）
时间复杂度：O(m log n)
优化与迪杰斯特拉的堆优化类似，此处略
二、Kruskal（克鲁斯卡尔）算法
克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（e log e）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树。
适用情况：稀疏图
时间复杂度：O(m log m)
思路
- 将所有边按权重从小到大排序（此处调用
sort 就可以）
- 枚举每一条边
- 如果这一条边两边不连通，加入这一条边
详解
见代码注释
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m;
int p[N];
// 用结构体存储图
struct Edge
{
int a, b, w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
} edges[N];
// 并查集-查找祖宗
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main()
{
// 输入
scanf("%d %d", &n, &m);
int a, b, w;
for (int i = 0 ; i < m ; ++i)
{
scanf("%d %d %d", &a, &b, &w);
edges[i] = {a, b, w};
}
// 排序
sort(edges, edges + m);
// 初始化并查集
for (int i = 1 ; i <= n ; ++i)
p[i] = i;
// 从小到大枚举所有边
int res = 0, cnt = 0;
for (int i = 0 ; i < m ; ++i)
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
// 查找祖宗
a = find(a), b = find(b);
// 如果不连通
if (a != b)
{
res += w, ++cnt;
// 合并并查集
p[a] = b;
}
}
// 输出
if (cnt < n - 1)
printf("impossible\n");
else
printf("%d\n", res);
return 0;
}
[复制链接]
发表于 2023-1-1 18:16
|
发表于 2023-1-2 08:42
