文章目录
一、前言
最小生成树定义：
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。
最小生成树其实是最小权重生成树的简称
二、Pirm算法求最小生成树
时间复杂度 O(n^2)
Prim 算法采用的是一种贪心的策略。（Prim算法和Dijkstra算法思路相似）
Prim算法简述
每次将离连通部分的最近的点和点对应的边加入的连通部分，连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小。
实现步骤
int prim() {
memset(dist, 0x3f, sizeof dist);//初始化为无限大
for (int i = 0; i < n; i++) {//遍历n个点
//1.找到集合距离最近的点
int t = -1;//初始化为没有找到的点
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[j] < dist[t])) {
t = j;//更新
}
}
//不是第一个取出的节点，并且当前节点的距离为INF，表示没有和集合中点相连的边
if (i && dist[t] == INF) return INF;
//不是第一个取出的节点，是其他点与集合中的连接线（最小边）
if (i) res += dist[t];
//2.更新当前最短边权点t到集合的距离（保留最小的值，如果比之前最短t到集合的距离还小，更新）
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], g[t][j]);
}
st[t] = true;//加入集合
}
return res;
}Prim算法与Dijkstra算法的区别
//Dijkstra算法是更新不在集合中的点 离起点的距离
dist[j]=min(dist[j], dist[t]+g[t][j])
Prim是更新不在集合中的点 离集合S的距离
dist[j] = min(dist[j], g[t][j])
例题：
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int dist[N], g[N][N]; // 存储其他点到当前最小生成树的距离，邻接矩阵，存储所有边
int n, m;
bool st[N]; // 存储每个点是否已经在生成树中
int res = 0;
int prim() {
memset(dist, 0x3f, sizeof dist);//初始化距离数组为一个很大的数
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[j] < dist[t])) {
t = j;
}
}
if (i && dist[t] == INF) return INF;
st[t] = true;
if (i) res += dist[t];
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], g[t][j]);
}
}
return res;
}
int main() {
memset(g, 0x3f, sizeof g);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin>>a>>b>>c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = prim();
if (t == INF) cout<<"impossible"<<endl;
else cout << t << endl;
}
记录最小生成树路径
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int g[N][N];//存储图
int dt[N];//存储各个节点到生成树的距离
int st[N];//节点是否被加入到生成树中
int pre[N];//节点的前去节点
int n, m;//n 个节点，m 条边
void prim()
{
memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数（10亿左右）
int res= 0;
dt[1] = 0;//从 1 号节点开始生成
for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树
{
int t = -1;
for(int j = 1; j <= n; j++)//每个节点一次判断
{
if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果没有在树中，且到树的距离最短，则选择该点
t = j;
}
st[t] = 1;// 选择该点
res += dt[t];
for(int i = 1; i <= n; i++)//更新生成树外的点到生成树的距离
{
if(dt[i] > g[t][i] && !st[i])//从 t 到节点 i 的距离小于原来距离，则更新。
{
dt[i] = g[t][i];//更新距离
pre[i] = t;//从 t 到 i 的距离更短，i 的前驱变为 t.
}
}
}
}
void getPath()//输出各个边
{
for(int i = n; i > 1; i--)//n 个节点，所以有 n-1 条边。
{
cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号，pre[i] 是 i 节点的前驱节点。他们构成一条边。
}
}
int main()
{
memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数
cin >> n >> m;//输入节点数和边数
while(m --)
{
int a, b, w;
cin >> a >> b >> w;//输出边的两个顶点和权重
g[a][b] = g[b][a] = min(g[a][b],w);//存储权重
}
prim();//求最小生成树
getPath();//输出路径
return 0;
}
三、Pirm算法堆优化
时间复杂度O(m∗logn)
很少用，时间复杂度高的时候可以考虑kruskal算法，实现简单
堆优化Prim相比于Kruskal难写一些，也没有效率上的优势，所以基本上没人写。
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=510;
int g[N][N],dist[N];
bool st[N];
int n,m;
int prim()
{
int res=0,tt=0;
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,1});
while(heap.size())
{
PII t = heap.top();
heap.pop();
int t1 = t.first,t2 = t.second;
for(int i=1;i<=n;i++)
{
if(st[t2]) continue;
st[t2]=true;
tt++;
if(t2>1) res+=dist[t2];
for(int j=1;j<=n;j++)
{
if(dist[j]>g[t2][j])
{
if(!st[j])
{
dist[j] = g[t2][j];
heap.push({dist[j],j});
}
}
}
}
}
if(tt!=n) return -1;
return res;
}
int main()
{
memset(g,0x3f,sizeof g);
cin>>n>>m;
for(int i=0;i<m;i++)
{
int u,v,w;
cin>>u>>v>>w;
g[u][v]=g[v][u]= min(g[u][v],w);
}
int t = prim();
if(t==-1) cout<<"impossible";
else cout<<t;
return 0;
}
最后
莫言真理无穷尽，寸进自有寸进欢
