最小生成树之 Prim 算法学习笔记
emm...在一通瞎搞奋战之后,prim被我收入囊中!
\(prim\) 的思路其实非常简单,和 \(dij\) 有一丝相似之处,可能会搞混
设最小生成树上的集合为 \(S\),所有点一开始到 \(S\) 的距离都是 \(+ \infty\)
从任意一个点开始,将其放入 \(S\) ,然后更新与这个点相邻的点到 \(S\) 的距离
再找到不在 \(S\) 中的且离 \(S\) 距离最小的点\(^{(注释1)}\),将其放入 \(S\) 然后更新与这个点相邻的点到 \(S\) 的距离
不断重复上一步直至所有的点都在 \(S\) 之中,最小生成树就这么建好了
注释1:
对于这一步有两种实现方式:
法一:直接暴力遍历所有的点 复杂度 \(O(n)\)
这样实现的话总复杂度为 \(O(n^2+m)\)
法二:用优先队列堆对结构来找 复杂度 \(O(log\ m)\)
这样的总复杂度为 \(O((n+m) \ log \ n)\)
当边数m很大时,法二的复杂度还不如暴力的法一
所以 当图为稀疏图时用法二 当图为稠密图时用法一
细节见代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edge
{
int f,t;
int w;
};
edge edges[1000000];
struct node
{
bool done;
int dis=1000000000;
vector<int > to;
};
node nodes[100000];
int ans;
priority_queue<pair<int,int> ,vector<pair<int,int> > ,greater<pair<int,int> > > q;
int prim()
{
q.push({0,1});
pair<int ,int > now_;
int the_bian,the_dis,to_;
int tot_dis=0,had_chosen=0;
while(!q.empty())
{
now_=q.top();
q.pop();
the_bian=now_.second;
the_dis=now_.first;
if(nodes[the_bian].done==0)//如果不在S中
{
nodes[the_bian].done=1;
tot_dis+=the_dis;
had_chosen++;
for(int yy=0;yy<nodes[the_bian].to.size();yy++)//遍历所有出边
{
to_=edges[nodes[the_bian].to[yy]].t;
if(nodes[to_].done==0)
{
if(edges[nodes[the_bian].to[yy]].w<nodes[to_].dis)//如果距离比之前的进,则更新,入队
{
nodes[to_].dis=edges[nodes[the_bian].to[yy]].w;//更新距离
q.push({nodes[to_].dis,to_});//入队
}
}
}
}
else
{
continue;
}
}
if(had_chosen<n)
{
return -99999;
}
else
{
return tot_dis;
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
int a,b,c;
for(int ee=1;ee<=m;ee++)
{
cin>>a>>b>>c;//建边
edges[ee].f=a;
edges[ee].t=b;
edges[ee].w=c;
edges[ee+m].f=b;
edges[ee+m].t=a;
edges[ee+m].w=c;
nodes[a].to.push_back(ee);
nodes[b].to.push_back(ee+m);
}
ans=prim();
if(ans==-99999)
{
cout<<"orz";
}
else
{
cout<<ans;
}
return 0;
}
//prim
标签:Prim,int,复杂度,笔记,ee,算法,edges,nodes,dis
From: https://www.cnblogs.com/sea-and-sky/p/18414455