最小生成树算法常见的有两种 Prim算法和Kruskal算法，两种算法所用的数据结构有所差异。 1.读入边 2.kruskal
#include<iostream> #include<cstdio> using namespace std; const int maxn=20010; struct edge { int u; int v; int w; edge(int _u,int _v,int _w):u(_u),v(_v),w(_w) {} edge() {} }; vector<edge> a; int m,n; bool cmp(edge a,edge b) { return a.w<b.w; } int find(int x) { return v[x]==x?x:v[x]=find(v[x]); } void read() { int u,v,w; scanf("%d %d",&n,&m); for(int i=0;i<m;i++) { scanf("%d %d %d",&u,&v,&w); a.push_back(e(u,v,w)); } } void kruskal() { int ans=0; for(int i=0;i<n;i++) v[i]=i; sort(a.begin(),a.end(),cmp); for(int i=0;i<m;i++) { int x=find(a[i].u); int y=find(a[i].v); if(x==y) continue; else { ans+=a[i].w; v[x]=y; } } return ans; }从小到大选取最小边，判断选取的边是否能够构成环，如果可以就不加入这条边，如果不行就加上，直到所有的边都找完，也可以通过判断是否加入的边等于n-1，如果最后小于n-1，则这图并不是连通的，如果到了n-1那么就不用再判断后面的边是否需要加入了。
