kruskal求最小生成树流程

### Kruskal算法求解最小生成树的具体流程 #### 一、初始化阶段 在开始之前，假设所有节点都是独立的连通分量。这意味着每个顶点自成一体，互不相连。 #### 二、边的选择与排序 将图中所有的边按照权重从小到大进行排序[^1]。这一操作确保每次选取的下一条边总是当前可用边缘中最轻的一条。 #### 三、构建最小生成树的过程 遍历已排序好的边列表，在每一步尝试加入新的边至正在形成的MST(最小生成树)，但需满足两个条件之一： - 如果这条边连接着两个不同的连通分量，则可以安全地将其添加进来而不形成回路； - 若两端属于同一个集合则跳过此边以防止创建循环结构[^2]。 当所选入MST内的边数量达到`V−1`(其中V代表总的顶点数目)时停止迭代；此时要么已经成功构造了一个完整的最小生成树，要么原图本身是非连贯状态无法构成单一MST。 ```cpp #include <iostream> #include <vector> #include<algorithm> using namespace std; struct Edge { int src, dest, weight; }; class DisjointSets { private: vector<int> parent, rank; public: DisjointSets(int n); int find(int v); // 查找并压缩路径 void Union(int x, int y); // 按秩合并 }; DisjointSets::DisjointSets(int n){ parent.resize(n),rank.resize(n,0); for (int i=0;i<n;++i) parent[i]=i; } // 路径压缩查找函数 int DisjointSets::find(int v){ if(v != parent[v]) parent[v] = find(parent[v]); return parent[v]; } void DisjointSets::Union(int x,int y){ int rootX=find(x); int rootY=find(y); if(rootX!=rootY){ if(rank[rootX]>rank[rootY]){ parent[rootY]=rootX; }else{ parent[rootX]=rootY; if(rank[rootX]==rank[rootY]) ++rank[rootY]; } } } bool compare(const struct Edge& a,const struct Edge &b){return a.weight<b.weight;} void kruskalMST(vector<Edge>& edges,vector<pair<int,pair<int,int>> >& resultEdges ,int V){ sort(edges.begin(),edges.end(),compare); DisjointSets ds(V); for(auto it : edges){ int u=it.src,v=it.dest,w=it.weight; int set_u=ds.find(u); int set_v=ds.find(v); if(set_u !=set_v){ resultEdges.push_back({w,{u,v}}); ds.Union(set_u,set_v); if(resultEdges.size()==V-1)// 当找到足够的边后退出 break; } } } ```