贪心算法最小生成树c++
时间: 2023-11-19 07:56:41 浏览: 56
贪心算法最小生成树是指在一个加权连通图中,找到一个生成树,使得树的所有边的权值之和最小。C++中可以使用Kruskal算法或Prim算法来实现最小生成树。
Kruskal算法的实现步骤如下:
1. 将所有边按照权重从小到大排序。
2. 初始化一个并查集,每个节点都是一个单独的集合。
3. 从权重最小的边开始,依次将边加入生成树中,如果加入该边不会形成环,则将该边加入生成树中,并将该边的两个节点合并为一个集合。
4. 重复步骤3,直到生成树中包含所有节点。
Prim算法的实现步骤如下:
1. 选择一个起始节点,将该节点加入生成树中。
2. 将与该节点相邻的所有边加入一个优先队列中。
3. 从优先队列中取出权重最小的边,如果该边的另一个节点不在生成树中,则将该边加入生成树中,并将该边的另一个节点加入生成树中。
4. 重复步骤3,直到生成树中包含所有节点。
相关问题
贪心算法解决最小生成树c++简单程序
贪心算法是一种常用的算法思想,可以用来解决很多问题,其中包括最小生成树问题。下面是一个简单的C++程序,用贪心算法求解最小生成树:
```C++
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int n, m;
int g[MAXN][MAXN];
int d[MAXN];
bool vis[MAXN];
int prim() {
fill(d, d + n + 1, INF);
fill(vis, vis + n + 1, false);
d[1] = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
int u = -1;
for (int j = 1; j <= n; j++) {
if (!vis[j] && (u == -1 || d[j] < d[u])) {
u = j;
}
}
vis[u] = true;
ans += d[u];
for (int v = 1; v <= n; v++) {
if (!vis[v] && g[u][v] < d[v]) {
d[v] = g[u][v];
}
}
}
return ans;
}
int main() {
cin >> n >> m;
fill(g[0], g[0] + MAXN * MAXN, INF);
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u][v] = g[v][u] = w;
}
int ans = prim();
cout << ans << endl;
return 0;
}
```
程序中使用了邻接矩阵来存储图,使用了Prim算法来求解最小生成树。具体来说,程序中的prim函数实现了Prim算法的过程,首先初始化距离数组d和访问数组vis,然后从第一个节点开始,每次选择距离最小的未访问节点,并将其加入生成树中,同时更新距离数组d。最后返回生成树的权值和即可。
最小生成树贪心算法c++编码
以下是Prim算法的C++实现,用于求解带权无向图的最小生成树:
```c++
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
int n,m;
int head[N],ver[N<<1],edge[N<<1],Next[N<<1],tot;
int dis[N],vis[N],cnt;
void add(int x,int y,int z){
ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
void prim(){
memset(dis,INF,sizeof(dis));
dis[1]=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
q.push(make_pair(0,1));
while(q.size()){
int x=q.top().second;q.pop();
if(vis[x]) continue;
vis[x]=1,cnt++;
for(int i=head[x];i;i=Next[i]){
int y=ver[i],z=edge[i];
if(dis[y]>z&&!vis[y]){
dis[y]=z;
q.push(make_pair(dis[y],y));
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
prim();
if(cnt<n) puts("impossible");
else{
int ans=0;
for(int i=1;i<=n;i++) ans+=dis[i];
printf("%d\n",ans);
}
return 0;
}
```