最小生成树的Kruskal算法

Myth丶恋晨 2022-08-18 11:57 177阅读 0赞

Kruskal算法的主要思想是按照边的权重顺序（从小到大）处理他们，将边加入最小生成树中，加入的边不会和已经加入的边构成环，直到树中含有V-1条边为止。

Kruskal算法能够计算任意加权连通图的最小生成树。

数据结构：

用优先队列来对边按照权重排序

用并查集(之前博客里提到过的union-find)来识别会形成环的边

用链表来保存最小生成树的所有边

时间复杂度ElgE

\-UF.h 并查集

#ifndef __UF_H__
    #define __UF_H__
    
    class UF {
    private:
    	int		*id;		// 父节点数组
    	int		*sz;		// 各个根节点对应的分量的大小
    	int		count;		// 连通分量的数量
    
    public:
    	UF(int n);
    	~UF() { delete[] id; delete[] sz; }
    
    	int getCount()const { return count; }
    	bool connected(int p, int q)const { return find(p) == find(q); }
    	int find(int p)const;
    
    	void myUnion(int p, int q);
    
    };
    
    UF::UF(int n) {
    	id = new int[n];
    	sz = new int[n];
    	count = n;
    	for (int i = 0; i < n; ++i) {
    		id[i] = i;
    		sz[i] = 1;
    	}
    }
    
    int UF::find(int p)const {
    	while (p != id[p]) {
    		p = id[p];
    	}
    	return p;
    }
    
    void UF::myUnion(int p, int q) {
    	int pID = find(p);
    	int qID = find(q);
    	if (pID == qID) return;
    	if (sz[pID] < sz[qID]) {
    		sz[qID] += sz[pID];
    		id[pID] = qID;
    	}
    	else {
    		sz[pID] += sz[qID];
    		id[qID] = pID;
    	}
    	--count;
    }
    
    #endif

\-KruskalMST.h

#ifndef __KRUSKAL_MST_H__
    #define __KRUSKAL_MST_H__
    
    #include "UF.h"
    #include "Edge.h"
    #include "EdgeWeightedGraph.h"
    #include <list>
    #include <vector>
    #include <functional>
    #include <queue>
    
    class KruskalMST {
    private:
    	std::list<Edge> mst;
    	double weight;
    
    public:
    	KruskalMST(const EdgeWeightedGraph& G) {
    		weight = 0.0;
    		int vNum = G.getV();
    		// 构造最小堆
    		std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge> > pq;
    		for (Edge e : G.edges()) {
    			pq.push(e);
    		}
    		UF uf(vNum);
    		int v, w;
    		Edge e;
    		while(mst.size() != vNum - 1) {
    			e = pq.top();
    			pq.pop();
    			v = e.either();
    			w = e.other(v);
    
    			if (uf.connected(v, w)) continue;
    			uf.myUnion(v, w);
    			// 添加进最小生成树
    			mst.push_back(e);
    			weight += e.getWeight();
    		}
    	}
    
    	std::list<Edge> edges()const { return mst; }
    	double getWeight()const { return weight; }
    
    };
    
    #endif

\-main.cpp 测试用例

#include "KruskalMST.h"
    #include "EdgeWeightedGraph.h"
    #include <iostream>
    #include <functional>
    using namespace std;
    
    int main()
    {
    	int vNum, eNum;
    	cin >> vNum >> eNum;
    
    	EdgeWeightedGraph G(vNum);
    
    	int v, w;
    	double weight;
    	for (int i = 0; i < eNum; ++i) {
    		cin >> v >> w >> weight;
    		G.addEdge(Edge(v, w, weight));
    	}
    
    	KruskalMST kruskalMST(G);
    	for (Edge e : kruskalMST.edges()) {
    		cout << e.either() << "-"
    			<< e.other(e.either()) << " "
    			<< e.getWeight() << endl;
    	}
    	cout << "total weight: " << kruskalMST.getWeight();
    
    	return 0;
    }

![SouthEast][]

[SouthEast]: /images/20220731/3844ea8ed36f4b1898965bac722b71f1.png