最小生成树：在无向图中，连接所有的点，不形成环，使所有的边权值和最小的树
算法有：prim算法： dijkstra算法类似（dis[i]的含义不同，dijkstra中是起点，prim中是已经访问过的所有点） 稠密图时使用 O(V^2)
kruskal算法：并查集思想，每次都找到最小的边，判断这两个边连接的点是不是在同一个集合中，如果不是就连接起来 稀疏图时使用 O(ElogE)
struct node{
int v,dis;
node(int _v,int _dis) : v(_v),dis(_dis){}
};
vector<node> adj[maxn];
int dis[maxn],vis[maxn];
int n,m,st,ed;
void prim(int st){
//树的总权值，以及当前所有的连接好了的边
for(int i=0;i<n;i++){
int u=-1,mini=INF; //与dijkstra是不是超级像！！！！！
for(int j=0;j<n;j++){
if(mini>dis[j]&&vis[j]==0) {
mini=dis[j];
u=j;
}
}
if(u==-1) return;
vis[u]=1;
ans+=dis[u]; //！！！！！啊啊啊记住这个
for(int j=0;j<adj[u].size();j++){
int id=adj[u][j].v;
int diss=adj[u][j].dis;
if(!vis[id]&&dis[id]>diss){
dis[id]=diss;//！！！！
}
}
}
}
kruskal
struct edge{
int from,to;
int dis;
}E[maxn];
int fa[maxn];
int findfather(int x){
if(x!=fa[x]) return findfather(fa[x]);
return fa[x];
}
bool cmp(edge a,edge b){
return a.dis<b.dis;
}
void kruskal(int n,int m){
//n是顶点数，m是边数
for(int i=0;i<n;i++) fa[i]=i; //先弄这个
fill(dis,dis+maxn,INF);
memset(vis,0,sizeof(vis));
dis[0]=0;
int ans=0,numedge=0; //这里才有！！总的权值和现在有了的边
sort(E,E+m,cmp); //对边进行排序
for(int i=0;i<m;i++){
int fa1=findfather(E[i].from);
int fa2=findfather(E[i].to);
if(fa1!=fa2){
fa[fa2]=fa1;
numedge++;
ans+=E[i].dis;
if(numedge==n-1) break; //!!!!!!!如果边数已经够了的话就可以break了
}
}
if(numedge!=n-1) {
cout<<"error no liantong"<<endl;
return;
}
else{
cout<<ans<<endl;
return;
}
}
原文：https://www.cnblogs.com/shirlybaby/p/12489263.html