【图论】最小生成树｜Prim+Kruskal算法

文章目录

• 最小生成树
• • 定义
  • 核心性质
  • Prim算法(加点法)
  • • 模板
    • • 朴素版（邻接矩阵+遍历）
      • 堆优化版（邻接矩阵+优先队列）
  • Kruskal算法（加边法）
  • • 模板
  • 模板题

最小生成树

最小生成树的算法：Prim算法和Kruskal算法

定义

适用场景：无向带权连通图

有向图没有最小生成树

最小生成树：在所有生成树里面，所有边权加起来总和最小的那一棵

选取n-1条边使得图中所有节点连接到一起，并且边的权值和最小

核心性质

Prim算法(加点法)

适用于稠密图

每次寻找距离最小生成树最近的节点并加入到最小生成树中。prim算法核心就是以下三步：

ans数组用来记录每一个节点距离最小生成树的最近距离

模板

朴素版（邻接矩阵+遍历）

//orz orz orz
#include<bits/stdc++.h>
#define ll long long
#define endl '\\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ull unsigned long long
#define fi first
#define se second
#define PLL pair<ll, ll>
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
using namespace std;
const ll MAXN=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
using namespace std;
ll v,e;
ll x,y,k;

int main()
{
IOS
cin>>v>>e;
vector<vector<ll>>g(v+1,vector<ll>(v+1,MAXN));
//邻接矩阵存无向图
while(e—)
{
cin>>x>>y>>k;
g[x][y]=k;
g[y][x]=k;
}
vector<ll>ans(v+1,MAXN);// 所有节点到最小生成树的最小距离
vector<bool>inT(v+1,false); // 这个节点是否在树里
ans[1]=0;
// 只需要循环 n-1次，建立 n – 1条边就可以把n个节点的图连在一起
for(ll i=1;i<=v–1;i++)
{
//选距离生成树最近节点
ll id=–1;
ll minv=LLONG_MAX;
for(ll j=1;j<=v;j++)
{
// 选取最小生成树节点的条件：
// （1）不在最小生成树里
// （2）距离最小生成树最近的节点
if(!inT[j]&&ans[j]<minv)
{
minv=ans[j];
id=j;
}
}
//最近节点（id）加入生成树
inT[id]=true;
for(ll j=1;j<=v;j++)
{
//更新非生成树节点到生成树的距离（即更新ans数组）
// 更新的条件：
// （1）节点是非生成树里的节点
// （2）与id相连的某节点的权值比该某节点距离最小生成树的距离小
if(!inT[j]&&g[id][j]<ans[j])
{
ans[j]=g[id][j];
}
}
}
ll res=0;
for(ll i=2;i<=v;i++)
{
res+=ans[i];
}
cout<<res<<endl;

//cout<<fixed<<setprecision(x)<< ;
return 0;
}

堆优化版（邻接矩阵+优先队列）

#include<bits/stdc++.h>
#define ll long long
#define endl '\\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ull unsigned long long
#define fi first
#define se second
#define PLL pair<ll, ll>
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
using namespace std;
const ll MAXN=11000;
const ll inf=0x3f3f3f3f;
using namespace std;
ll n,m;
int main()
{
IOS
cin>>n>>m;
vector<vector<PLL>>e(n+1);
vector<bool>vis(n+1,false);
vector<ll>dis(n+1,inf);
priority_queue<PLL,vector<PLL>,greater<PLL>>q;
for(ll i=1;i<=m;i++)
{
ll u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
dis[1]=0;
q.push({0,1});
ll res=0,cnt=0;
while(!q.empty()&&cnt<n)
{
auto [w,u]=q.top();
q.pop();
if(vis[u])
{
continue;
}
vis[u]=true;
res+=w;
cnt++;
for(auto [v,w]:e[u])
{
if(!vis[v]&&w<dis[v])
{
dis[v]=w;
q.push({w,v});
}
}
}
cout<<(cnt==n?res:–1)<<endl;

//cout<<fixed<<setprecision(x)<< ;
return 0;
}

Kruskal算法（加边法）

适用于稀疏图

都是贪心思路

Kruskal算法和Prim算法解决的是同一个问题，两者区别在于prim算法是以点构建最小生成树的，而kruskal算法则是通过边和边构成最小生成树的

具体步骤

• 边的权值排序，因为要优先选最小的边加入到生成树里
• 遍历排序后的边
  • 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
  • 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

个人感觉 这么写下来还是 Kruskal 比Prim好理解 借助并查集就非常好理解 而且代码简单对并查集不太熟悉的可以戳这里【图论】并查集

模板

//orz orz orz
#include<bits/stdc++.h>
#define ll long long
#define endl '\\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ull unsigned long long
#define fi first
#define se second
#define PLL pair<string, ll>
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
using namespace std;
const ll MAXN=1100;
const ll mod=1e9+7;
using namespace std;
struct e{
ll l,r,v;
};
bool cmp(const e &a,const e &b)
{
return a.v<b.v;
}
ll p[MAXN];
void in(ll n)
{
for(ll i=1;i<=n;i++)
{
p[i]=i;
}
}
ll Find(ll x)
{
if(p[x]==x)
{
return x;
}
else
{
return p[x]=Find(p[x]);
}
}
void u(ll x,ll y)
{
ll nx=Find(x);
ll ny=Find(y);
if(nx!=ny)
p[nx]=ny;
}
bool same(ll u,ll v)
{
u=Find(u);
v=Find(v);
return u==v;
}
ll vv,ee;
ll l1,r1,v1;
ll res=0;
int main()
{
IOS
cin>>vv>>ee;
vector<e>ed;
while(ee—)
{
cin>>l1>>r1>>v1;
ed.push_back({l1,r1,v1});
}
sort(ed.begin(),ed.end(),cmp);
in(vv);
for(e ede:ed)
{
ll x=Find(ede.l);
ll y=Find(ede.r);
if(x!=y)
{
res+=ede.v;
u(x,y);
}
}
cout<<res<<endl;
//cout<<fixed<<setprecision(x)<< ;
return 0;
}

Kruskal 一定要写路径压缩并查集，否则会 TLE

Kruskal 与 prim 的关键区别在于，prim维护的是节点的集合，而 Kruskal 维护的是边的集合。 如果 一个图中，节点多，但边相对较少，那么使用Kruskal 更优。

模板题

53. 寻宝

完完全全就是一个模板题两种模板随便一个 就够用

#include<bits/stdc++.h>
#define ll long long
#define endl '\\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ull unsigned long long
#define fi first
#define se second
#define PLL pair<ll, ll>
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
using namespace std;
const ll MAXN=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
using namespace std;
ll v,e;
ll x,y,k;

int main()
{
IOS
cin>>v>>e;
vector<vector<ll>>g(v+1,vector<ll>(v+1,MAXN));
while(e—)
{
cin>>x>>y>>k;
g[x][y]=k;
g[y][x]=k;
}
vector<ll>ans(v+1,MAXN);
vector<bool>inT(v+1,false);
ans[1]=0;
for(ll i=1;i<=v–1;i++)
{
ll id=–1;
ll minv=LLONG_MAX;
for(ll j=1;j<=v;j++)
{
if(!inT[j]&&ans[j]<minv)
{
minv=ans[j];
id=j;
}
}
inT[id]=true;
for(ll j=1;j<=v;j++)
{
if(!inT[j]&&g[id][j]<ans[j])
{
ans[j]=g[id][j];
}
}
}
ll res=0;
for(ll i=2;i<=v;i++)
{
res+=ans[i];
}
cout<<res<<endl;

//cout<<fixed<<setprecision(x)<< ;
return 0;
}