微客导航 » 文章资讯 » C++使用Kruskal和Prim算法实现最小生成树

C++使用Kruskal和Prim算法实现最小生成树

2023-08-31 16:34:04 230

很久以前就学过最小生成树之Kruskal和Prim算法，这两个算法很容易理解，但实现起来并不那么容易。最近学习了并查集算法，得知并查集可以用于实现上述两个算法后，我自己动手实现了最小生成树算法。

宏观上讲，Kruskal算法就是一个合并的过程，而Prim算法是一个吞并的过程，另外在Prim算法中还用到了一种数据结构——优先级队列，用于动态排序。由于这两个算法很容易理解，在此不再赘述。接下来给出我的源代码。

输入

第一行包含两个整数n和m，n表示图中结点个数，m表示图中边的条数；接下来m行，每一行包含三个整数u,v,w，表示途中存在一条边(u,v)，并且其权重为w；为了便于调试，我的程序是从文件中输入数据的；

输出

输出程序选择的最小生成树的权值之和以及每一条边信息；

Kruskal算法：

#include
#include
#include
#include
usingnamespacestd;

structEdge
{
intu;//边连接的一个顶点编号
intv;//边连接另一个顶点编号
intw;//边的权值
friendbooloperator<(constEdge&E1,constEdge&E2)
{
returnE1.w&uset,intn)
{
uset.assign(n,0);
for(inti=0;i&uset,intu)
{
inti=u;
while(uset[i]!=i)i=uset[i];
returni;
}
voidKruskal(constvector&edges,intn)
{
vectoruset;
vectorSpanTree;
intCost=0,e1,e2;
MakeSet(uset,n);
for(inti=0;i>n>>m;
vectoredges;
edges.assign(m,Edge());
for(inti=0;i>edges[i].u>>edges[i].v>>edges[i].w;
sort(edges.begin(),edges.end());//排序之后，可以以边权值从小到大的顺序选取边
Kruskal(edges,n);

in.close();

system("pause");
return0;
}

Prim算法：

#include
#include
#include
#include
#include
usingnamespacestd;
structNode
{
intv;
intw;
Node(inta,intb):v(a),w(b){}
};
structEdge
{
intu;
intv;
intw;
Edge(inta,intb,intc):u(a),v(b),w(c){}
friendbooloperator<(constEdge&E1,constEdge&E2)
{
returnE1.w>E2.w;
}
};
intn,m;
vector>Adj;
priority_queueQ;

intFindSet(vector&uset,intv)
{
inti=v;
while(i!=uset[i])i=uset[i];
returni;
}

voidPrim()
{
intCost=0;//用于统计最小生成树的权值之和
vectorSpanTree;//用于保存最小生成树的边
vectoruset(n,0);//用数组来实现并查集
EdgeE(0,0,0);
for(inti=0;iv,it->w));//根据Prim算法，开始时选取结点0，并将结点0与剩余部分的边保存在优先队列中
//循环中每次选取优先队列中权值最小的边，并更新优先队列
while(!Q.empty())
{
E=Q.top();
Q.pop();
if(0!=FindSet(uset,E.v))
{
Cost+=E.w;
SpanTree.push_back(E);
uset[E.v]=E.u;
for(autoit=Adj[E.v].begin();it!=Adj[E.v].end();it++)
if(0!=FindSet(uset,it->v))Q.push(Edge(E.v,it->v,it->w));
}
}
cout<<"Result:\n";
cout<<"Cost:"<>n>>m;
Adj.assign(n,list());
for(inti=0;i>u>>v>>w;
Adj[u].push_back(Node(v,w));
Adj[v].push_back(Node(u,w));
}
Prim();

in.close();

system("pause");
return0;
}

就实现而言，Kruskal算法比Prim算法更容易，代码更易于理解。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

返回顶部
3162201930
czq8825@qq.com

C++使用Kruskal和Prim算法实现最小生成树

热门推荐

随机推荐