前言
两者思路都为贪心。
Kruskal是通过对所有边排序，每次找不会成环的权值最小边。
Prim是找到未更新的最近节点，用该节点对其他未更新节点进行松弛，标记该节点已更新，再重复上述直至全部节点更新。
稀疏图：Kruskal 优
稠密图：Prim 优。
当然也可在阿鑫的半成品个人博客网站上阅读：阿鑫的学习小站
题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。
输入格式
第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。
接下来 M 行每行包含三个整数 X i ,Y i,Z i，表示有一条长度为 Z i 的无向边连接结点 X i ,Y i。
输出格式
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
输入输出样例
输入
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出
7
Kruskal
时间复杂度：O(MlogM)
思路： 对所有边依据权值从小到大排序 , 按顺序找出 n-1条 可用边（即不会成环的边）
思路 一> code：
1.对所有边依据权值从小到大排序
一> 用优先队列存储边，对于边可以构造一个结构体，记录 起点、终点、权值
2.队列空前找出 n-1条 可用边（即不会成环的边）
一> 从队首不断读取和弹出头节点（当前最短边），利用 并查集 判断是否成环（如果已经在集合内，则会成环，舍去），如果不成环则取用该边，将其加入生成树集合。如果队空前已找到了 n-1条 边可提前结束
ac题解
//用时：258ms(O2优化:138ms) 内存：4.36MB
#include <bits/stdc++.h>
using namespace std;
struct node{
int x;
int y;
int z;
//对结构体的 > 重载 ,否则 greater<node>用不了
bool operator > (const node& _T)const
{
return z > _T.z;
}
};
priority_queue<node,vector<node>,greater<node> > q;
/* 上述还可写成下面这种形式
struct node{
int x;
int y;
int z;
};
struct cmp
{
template <typename T>
bool operator()(T const &a, T const &b)
{
return a.z>b.z;
}
};
priority_queue<node,vector<node>,cmp> q;
*/
//并查集模板
long long ans;
int par[5005];
void init(int n,int par[]){
for(int i=1;i<=n;i++)
par[i]=i;
}
int find(int x){
if(par[x]==x){
return x;
}else{
par[x]=find(par[x]);
return par[x];
}
}
int merge(int x,int y){
int tx,ty;
tx=find(x);
ty=find(y);
if(tx==ty){ //如果在一个集合，返回0
return 0;
}else{ //不在一个集合，合并两集合，返回1
par[ty]=tx;
return 1;
}
}
//主函数
int main()
{
int i,j,n,m;
int flag; //记录 取到边 的数目
cin>>n>>m;
for(i=1;i<=m;i++){
node t;
scanf("%d%d%d",&t.x,&t.y,&t.z);//按题意输入
q.push(t); //压入优先队列完成排序
}
init(n,par); //初始化集合
while(!q.empty()&&flag<n-1){ //队不为空(还有边没判断)，且没找到n-1条边
node t=q.top(); //取出当前最短边
if(merge(t.x,t.y)){ //不在同一集合则该边可取
flag++;
ans+=t.z;
}
q.pop(); //弹出该边
}
if(flag==n-1) cout<<ans<<endl; //找到了n-1条边，输出答案
else cout<<"orz"<<endl; //否则无法生成最小生成树
return 0;
}
Prim
时间复杂度：
思路：
思路 一> code：
ac题解
#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int>, vector<pair<int, int> >,greater<pair<int,int> > > q;
//greater<pair<int,int>会先比较.first如果相等再比较.second
vector<pair<int,int> > a[5005];
int dis[5005];
long long ans;
int book[5005];
int main()
{
memset(dis,0x3f,sizeof(dis)); //初始化默认距离都为 很大
int i,j,n,m;
int x,y,z;
cin>>n>>m;
for(i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z); //输入并用邻接表存储
a[x].push_back(make_pair(y,z));
a[y].push_back(make_pair(x,z));
}
int t=1; //将 结点1 作为 起点
dis[t]=0;
book[t]=1;
int mn = 999999999;
for(i=1;i<n;i++){
for(j=0;j<a[t].size();j++){ //遍历与 t 相邻的结点
if(book[a[t][j].first]==0){ //如果未被访问
dis[a[t][j].first] = min(dis[a[t][j].first],dis[t]+a[t][j].second);//松弛
q.push(make_pair(a[t][j].second,a[t][j].first)); //将该点压入优先队列
}
}
if(q.empty()) break;
while(!q.empty()){ //找到未选过的最近点
t=q.top().second;
if(book[t]==1) q.pop();
else break;
}
if(book[t]==1) break;
ans+=q.top().first;
q.pop();
book[t]=1;
}
if(i==n) cout<<ans<<endl;
else cout<<"orz"<<endl;
return 0;
}