最小生成树算法：普里姆算法(Prim算法)＆克鲁斯卡尔算法(Kruskal算法)
学习笔记# 最小生成树问题
常用的最小生成树一般是无向图。
一般不对边的负权作要求。
## 一、普里姆算法（Prim算法）
**普里姆算法**（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
### 1. 朴素版Prim算法
**适用情况**：稠密图
**时间复杂度**：O(n^2^)
#### 思路
1. 初始化距离（INF）
2. 迭代 n 次
1. 找到不在连通块中的距离最小的点
2. 用这个点更新其他点到**连通块**（注意与迪杰斯特拉算法的区别）的距离
3. 加入连通块
#### 详解
见代码注释
#### 代码
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;
int n, m;
int g; // 稠密图用邻接矩阵存储
int dist; // 每个点到连通块的距离
bool st; // 这个点是否在连通块内
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 && (t == -1 || dist > dist))
t = j;
// 图不连通，没有最小生成树
if (i && dist == INF)
return INF;
if (i) // 如果不是第一个点
res += dist; // 结果中加入边
// 更新距离
for (int j = 1 ; j <= n ; ++j)
dist = min(dist, g);
// 加入连通块
st = 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 = g = min(g, 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)
#### 思路
1. 将所有边按权重从小到大排序（此处调用 `sort` 就可以）
2. 枚举每一条边
3. 如果这一条边两边不连通，加入这一条边
#### 详解
见代码注释
#### 代码
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m;
int p;
// 用结构体存储图
struct Edge
{
int a, b, w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
} edges;
// 并查集-查找祖宗
int find(int x)
{
if (p != x)
p = find(p);
return p;
}
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 = {a, b, w};
}
// 排序
sort(edges, edges + m);
// 初始化并查集
for (int i = 1 ; i <= n ; ++i)
p = i;
// 从小到大枚举所有边
int res = 0, cnt = 0;
for (int i = 0 ; i < m ; ++i)
{
int a = edges.a, b = edges.b, w = edges.w;
// 查找祖宗
a = find(a), b = find(b);
// 如果不连通
if (a != b)
{
res += w, ++cnt;
// 合并并查集
p = b;
}
}
// 输出
if (cnt < n - 1)
printf("impossible\n");
else
printf("%d\n", res);
return 0;
}
```
NO MORE, THANKS! 学习一下 好好学习，天天向上 你也是Y总的学生？{:1_929:} 当年奥赛支配的恐惧....... yxrhy_ming 发表于 2023-1-1 20:43
你也是Y总的学生？
啊对对对！ 不错不错，get到了 感谢分享，很实用的算法
页:
[1]