这个算法和Prim用法是一致的，但是得到的方式却大不相同，Prim是找任意一个结点连着的最小的边，从而不断更新到达各个结点的最小花费。时间复杂度是：O(n*n)，更适合稠密图;
而Kruskal算法是找到最小的边，看这条边的两点结点是否在相同的集合，如果是，说明形成回路，如果不是，及时更新两结点所在的集合，直至所有集合都是1。时间复杂度：O(eloge)，更适合稀疏图。
Prim算法实现：
#include <iostream>
#include <algorithm>
using namespace std;const int N = 100;
const int INF = 1e7;int n,m;
int map[N][N],closest[N],lowcost[N];
bool flag[N];void Prim(int u){for(int i=1;i<=n;i++){if(i!=u){lowcost[i]=map[u][i];closest[i]=u;}flag[i]=false;}flag[u]=true;lowcost[u]=0;for(int i=1;i<=n;i++){int temp=INF,t=u;for(int j=1;j<=n;j++){if(!flag[j]&&temp>lowcost[j]){temp=lowcost[j];t=j;}}if(t==u){break;}flag[t]=true;for(int j=1;j<=n;j++){if(!flag[j]&&lowcost[j]>map[t][j]){lowcost[j]=map[t][j];closest[j]=t;}}}
}int main(void){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){map[i][j]=INF;}}int u,v,w;while(m--){cin>>u>>v>>w;map[u][v]=w;map[v][u]=w;}int be;cout<<"请输入任意一个结点：";cin>>be;Prim(be);int sum=0;cout<<"数组lowcost的内容是：";for(int i=1;i<=n;i++){cout<<lowcost[i]<<" ";sum+=lowcost[i];}cout<<endl;cout<<"总的最少花费是："; cout<<sum<<endl;return 0;
}运行结果：
Kruskal算法：
有两种方式，一种是可以用一个数组来描述他们是否在同一个集合中。
另一种是用并查集来看是否在同一个集合中。
先来看第一种：
#include <iostream>
#include <algorithm>
using namespace std;const int N = 100;int n,m;
int nodeset[N]; //各个结点所属集合
struct Edge{int u,v,w;
}e[N*N];bool cmp(Edge x,Edge y){return x.w<y.w;
}int merge(int a,int b){int p=nodeset[a];int q=nodeset[b];if(p==q)return 0;else{for(int i=1;i<=n;i++){if(nodeset[i]==q){nodeset[i]=p;}}return 1;}
}int Kruskal(int n){int ans=0;for(int i=1;i<=m;i++){if(merge(e[i].u,e[i].v)){ans+=e[i].w;n--;if(n==1)return ans;}}return 0;
}int main(void){cin>>n>>m;for(int i=1;i<=n;i++){nodeset[i]=i;}for(int i=1;i<=m;i++){cin>>e[i].u>>e[i].v>>e[i].w;}sort(e+1,e+m+1,cmp);int ans=Kruskal(n);cout<<ans<<endl;return 0;
} 运行结果：
第二种方式：
#include <iostream>
#include <algorithm>
using namespace std;const int N = 100;int n,m;
int f[N]; //各个结点所属集合
struct Edge{int u,v,w;
}e[N*N];bool cmp(Edge x,Edge y){return x.w<y.w;
}int find(int x){if(x==f[x]){return x;}else{return find(f[x]);}
}int merge(int a,int b){int p=find(a);int q=find(b);if(p==q){return 0;}else if(p>q){f[p]=q;}else{f[q]=p;}return 1;
}int Kruskal(int n){int ans=0;for(int i=1;i<=m;i++){if(merge(e[i].u,e[i].v)){ans+=e[i].w;n--;if(n==1)return ans;}}return 0;
}int main(void){cin>>n>>m;for(int i=1;i<=n;i++){f[i]=i;}for(int i=1;i<=m;i++){cin>>e[i].u>>e[i].v>>e[i].w;}sort(e+1,e+m+1,cmp);int ans=Kruskal(n);cout<<ans<<endl;return 0;
} 运行结果：
