太原做网站 小程序/百度一下就知道官方

最小生成树的Kruskal算法采取贪心策略

即将图的各条边按照权值大小排序，依次从最小的边开始加入最小生成树

但是加入前需要确认加入的边不会使得原先构成环

基本思路：

初始化每个顶点为单独一个集合，每加入一条边后，合并边所在的2个顶点所属集合

每次加入边时需要确认边2边所属顶点集合不同

采取并查集实现集合合并与快速查询，采取路径压缩加速并查集

void UFSet()//初始化
{for (i = 0; i < n; i++)parent[i] = i;
}
int Find(int x)  //查找x节点的根
{if (x == parent[x])return x;int result = Find(parent[x]);//递归查找结果，递归返回前，先路径压缩parent[x] = result;return result;
}
void Union(int r1, int r2)
{int R1 = Find(r1);int R2 = Find(r2);parent[R1] = R2;
}

实现逻辑

void Kruskal()
{int sum = 0;int num = 0;//记录所选的边数目 不超过n-1int u, v;UFSet();//初始化并查集int the_num=0;for (i = 0; i < m; i++){u = edges[i].u;v = edges[i].v;if (Find(u) != Find(v))  //如果不在同一颗树上，那么合并它们{cout << u <<" "<< v<<" " << edges[i].w << endl;sum += edges[i].w;Union(u, v);the_num++;}if(the_num==n-1)break;}cout << " " << sum << endl;
}int main()
{int u, v, w;cin >> n >> m;for (int i = 0; i < m; i++){cin >>edges[i].u >>edges[i].v >>edges[i].w;}sort(edges, edges + m, cmp);Kruskal();return 0;
}