什么是最小生成树？
一幅加权图的最小生成树（MST）是它的一颗权值（树中的所有边的权值之和）最小的生成树.
这里介绍最小生成树的两种方法：Prim和Kruskal。
两者区别：Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。Prim是以更新过的节点的连边找最小值，Kruskal是直接将边排序。
两者其实都是运用贪心的思路
Prim：
个人觉得Prim和最短路中的dijkstra很像，由于速度问题，所以这里我用链式前向星存图。Prim的思想是将任意节点作为根，再找出与之相邻的所有边（用一遍循环即可），再将新节点更新并以此节点作为根继续搜，维护一个数组：dis，作用为已用点到未用点的最短距离。 证明：Prim算法之所以是正确的，主要基于一个判断：对于任意一个顶点v，连接到该顶点的所有边中的一条最短边(v, vj)必然属于最小生成树（即任意一个属于最小生成树的连通子图，从外部连接到该连通子图的所有边中的一条最短边必然属于最小生成树）
具体算法流程图解如下：
prim的写法：
void prim()
{
for(int i=1;i<=n;i++)dis[i]=map[1][i],visit[i]=0;//map指读入数据时，1点到所有点的距离，一般来说到不了就取231-1（int范围），visit为这个点搜过没有
visit[1]=true;//起点不用搜
for(int i=1;i<=n;i++)
{
int mi=2147483647,p=0;
for(int j=1;j<=n;j++)
{
if(visit[j]==0&&dis[j]<mi)
mi=dis[j],p=j;
}//找离它最近的点，mi求目前的最小，p为位置
if(p==0)break;//若所有点都试过，退出
visit[p]=true;//标记此点已搜过
for(int j=1;j<=n;j++)
if(map[p][j]<dis[j]&&visit[j]==0)//求最小，并且保证没搜过j点
dis[j]=map[p][j];//这里和dijkstra不一样，dijkstra是dis[j]=map[p][j]+dis[p];
}
}
Kruskal：
Kruskal算法的思想比Prin好理解一些。这个算法用到的方法是，先将所有边按照权重（此处是时间长短）排序，我是从小到大排序的。排序用到的算法复杂度只能是 O(nlgn)O(nlgn) 以下的，不然会超时。比如快速排序，这些必须学，此处不做赘述。排好序以后，就从权重最小的边开始，因为此时所有节点的祖先值都为自己（也就是所有的节点都是独立的），运用并查集进行查的操作，看一下边的左右节点的祖先是否相同，如果最老祖先相同，就代表这两个节点已经在一个树里面了，你再去连这两个节点，就会练成图，所以最老祖先相同则不连，如果有不同的最老祖先，那么就对这两个节点进行并的操作，这样还是树。直到最后，这个算法完毕后，最小树就生成了。
证明：刚刚有提到：如果某个连通图属于最小生成树，那么所有从外部连接到该连通图的边中的一条最短的边必然属于最小生成树。所以不难发现，当最小生成树被拆分成彼此独立的若干个连通分量的时候，所有能够连接任意两个连通分量的边中的一条最短边必然属于最小生成树。
具体算法流程图解如下：
Kruskal：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1000+10;
int n,m;
int father[maxn];
double ans;
bool cmp(data1 x,data1 y)//排序
{
return x.z<y.z;
}
int get(int x)//像不像并查集的找父亲
{
if(father[x]==x)return x;
return father[x]=get(father[x]);//路径压缩
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)father[i]=i;
for(int i=1;i<=m;i++)
cin>>f[i].x>>f[i].y>>f[i].z;//x和y是点，z是距离
int s=0;//合并个数
sort(f+1,f+1+m,cmp);//按边排序
for(int i=1;i<=m;i++)
{
int fx=get(f[i].x);//找父亲
int fy=get(f[i].y);//找父亲
if(fx!=fy)//他们不是一个父亲，合并两棵树
{
s++;//合并个数增加
ans+=f[i].z;//最小生成树长度加上边长
father[fy]=fx;//祖先的父亲指向另一个祖先
}
if(s==n-1)break;//如果已经合并了n-1次，代表着n棵以自己为结点的树已全部合并成一棵树
}
printf("%.2lf",ans);//输出最小生成树
return 0;
}
PS：由于个人码风习惯，代码可能看上去较长，但其实自己写起来还是比较短的。