生成树 : 如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树
最小生成树 : 边权和最小的生成树叫做最小生成树。如果原图不连通，则没有最小生成树
求最小生成树有两种方法 ： prim 和 kurskal
一. prim算法
将最小生成树看做一个集合，每次选取距离集合最近的点，如果这个点不在集合中则加入集合，也就意味着这个点和集合里的点所连成的边加入了集合。最后等到所有点都加入集合则所有进入集合的边构成最小生成树。
例题1 prim板子
给你一张 n 个顶点 m 条边的无向简单连通图，顶点编号从 1 到 n，每条边都有一个边权，边权为非负整数。
请求出这张图的最小生成树，只需要输出最小生成树的边权和即可。
输入格式
第一行两个整数 n,m 表示图的顶点数、边数。接下来 m 行，每行三个整数 x,y,z 表示 x 号点与 y 号点之间有一条边权为 z 的边。
数据保证图中顶点两两连通。
输出格式
输出一行一个数，表示最小生成树的边权和。
样例输入
4 4
1 2 1
2 3 3
3 4 1
1 4 2
样例输出
4
数据规模
对于所有数据，保证 2≤n≤1000,n−1≤m≤100000,1≤x,y≤n,1≤z≤10000
代码
# include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 1e4+10;
vector<pii> edge[N];
int dist[N]; //这里的dist是指点到集合（生成树）的距离
bool st[N];
int n,m;
int prime()
{
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
priority_queue<pii,vector<pii>,greater<pii> > q;
q.push({dist[1],1});
int ans = 0; //ans是最小生成树的权值和
int tot;tot = 0; //tot存的是集合中的点的数量，如果结束的时候tot ！= n则证明无法构造出生成树
while(q.size())
{
auto t = q.top();q.pop(); //找出距离集合最小的点
if(st[t.second]) continue; //每次取到集合最近的点，如果这个点已经在集合中则continue
tot++;
ans+=t.first;st[t.second] = true;
for(auto i:edge[t.second])
{
if(dist[i.first]>i.second) //注意这里dist要和边权比，因为边权最终是距离集合的距离
{
dist[i.first] = i.second;
q.push({dist[i.first],i.first});
}
}
}
if(tot!=n) return -1;
return ans;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int x,y,z;scanf("%d%d%d",&x,&y,&z);
edge[x].push_back({y,z});edge[y].push_back({x,z});
}
cout<<prime()<<endl;
return 0;
}
例题2
在一片海域上有 n
内容来源于网络如有侵权请私信删除文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
