算法-图论-最小生成树-KruskalMST

先排序，挑最小权值，并利用并查集判断不能形成环

#include <iostream>
#include <vector>
#include "MinHeap.h"
#include "UnionFind5.h"
#include "Edge.h"

using namespace std;
template <typename Graph,typename Weight>
class KruskalMST{
private:
    vector<Edge<Weight>> mst;
    Weight mstWeight;
public:
    KruskalMST(Graph &graph){
        MinHeap<Edge<Weight>> pq(graph.E());
        for(int i=0;i<graph.V();i++){
            typename Graph::adjIterator adj(graph,i);
            for(Edge<Weight> *e = adj.begin();!adj.end();e=adj.next()){
                if(e->v() < e->w())
                    pq.insert(*e);
            }
        }
        UnionFind5 uf(graph.V());//开顶点个数的空间 
        while (!pq.isEmpty() && mst.size()<graph.V()-1)
        {
            Edge<Weight> e pq.extractMin();
            if(uf.isConnected(e.v(),e.w()))
                continue;
            mst.push_back(e)
            uf.unionElements(e.v(),e.w());
        }
        //计算权值
        mstWeight = mst[0].wt();
        for(int i =1;i<mst.size();i++)
            mstWeight += mst[i].wt();
        
    }
    ~KruskalMST(){

    };
    vector<Edge<Weight>> mstEdge(){
        return mst;
    };
};