Prim算法原理和实现 Prim算法和Kruskal算法的区别

发布:2022-10-24 14:35:21
阅读:18750
作者:网络整理
分享:复制链接

Prim算法是一种贪心算法,用于从图中找到最小生成树。Prim算法找到包含图的每个顶点的边的子集,从而可以最小化边的权重之和。

Prim的算法从单个节点开始,并在每一步探索所有具有所有连接边的相邻节点。选择了具有最小权重的边,导致图中没有循环。

Prim算法的工作原理

算法的目的是找到全局最优值。从一个顶点开始,不断添加权重最低的边,直到找到目标。

Prim算法的实现步骤如下:

1、用随机选择的顶点初始化最小生成树。

2、找到将树连接到新顶点的所有边,找到最小值并将其添加到树中。

3、继续重复步骤2,直到得到最小生成树。

Prim算法的实现

简单地选择权重为1的边。在下一次迭代中,我们有三个选项,权重为2、3和4的边。因此,我们将选择权重为2的边并标记顶点。现在我们再次有三个选项,权重为3、4和5的边。但我们不能选择权重为3的边,因为它正在创建一个循环。所以我们将选择权重为4的边,最终得到总成本为7的最小生成树(=1+2+4)。

using namespace std;
const int MAX=1e4+5;
typedef pair<long long,int>PII;
bool marked[MAX];
vector<PII>adj[MAX];
long long prim(int x){
priority_queue<PII,vector<PII>,greater<PII>>Q;
int y;
long long minimumCost=0;
PII p;
Q.push(make_pair(0,x));
while(!Q.empty())
{
p=Q.top();
Q.pop();
x=p.second;
if(marked[x]==true)
continue;
minimumCost+=p.first;
marked[x]=true;
for(int i=0;i<adj[x].size();++i)
{
y=adj[x]<i>.second;
if(marked[y]==false)
Q.push(adj[x]<i>);
}
}
return minimumCost;}
int main(){
int nodes,edges,x,y;
long long weight,minimumCost;
cin>>nodes>>edges;
for(int i=0;i<edges;++i)
{
cin>>x>>y>>weight;
adj[x].push_back(make_pair(weight,y));
adj[y].push_back(make_pair(weight,x));
}
minimumCost=prim(1);
cout<<minimumCost<<endl;
return 0;}

Prim算法和Kruskal算法的区别

Prim算法

1、从图中的任何顶点构建最小生成树

2、遍历一个节点不止一次以获得最小距离

3、Prim算法给出了连通分量,并且它只适用于连通图

4、Prim算法在密集图中运行得更快

5、从根顶点开始生成最小生成树

6、Prim算法更适合列表数据结构

Kruskal算法

1、从图中权重最小的顶点开始构建最小生成树

2、只遍历一个节点一次

3、Kruskal算法可以在任何时刻生成森林,也可以在断开的组件上工作

4、Kruskal算法在稀疏图中运行得更快

5、从权重最小的边开始生成最小生成树

6、Kruskal的算法更喜欢堆数据结构

扫码进群
微信群
免费体验AI服务