2021-1 贪心算法 最小生成树 Kruskal算法 c++实现

基本原理

• 基础定义点这里了解 最小生成树理论准备
• 假定树有V个顶点，按照边的权重由小到大处理，将边加入到最小生成树中，且加入的边不会和已经加入的边构成环，直到树中含有V-1条边为止。

黑色边为树，灰色为无用边，所有灰色和所有白色节点构成一个切分，右侧边按权重排序。

几个关键

• 按照权重排序边，用一条优先队列。
• 合并森林中的两棵树并识别环，用并查集。
• 用一条队列来保存树的各个边。

实现

不失重点的，先看如何写好 Kruskal算法 。并查集，优先队列等工具放在文末。

#pragma once
#include<queue>
#include"EdgeWeightGraph.h"
#include"UF.h"typedef  priority_queue<Edge, vector<Edge>, greater<Edge> > MinPQ;class KruskalMST
{
    
public:KruskalMST(EdgeWeightGraph& G);queue<Edge>* edges() {
     return m_mst; }//返回生成树double weight();//计算总权重
private:queue<Edge>* m_mst;
};void testForKruskalMST();

#include "KruskalMST.h"KruskalMST::KruskalMST(EdgeWeightGraph& G)
{
    m_mst = new queue<Edge>();MinPQ* pq = new MinPQ();//所有边入队for (auto& e : *(G.edges()) ){
    pq->push(e);}UF* uf = new UF(G.V());while (!pq->empty() && m_mst->size() < G.V() - 1) {
    Edge e = pq->top(); pq->pop();//取出最短边int v = e.either(), w = e.other(v);if (uf->connected(v, w)) continue; //忽略失效的边uf->Union(v, w);//合并分量m_mst->push(e);//添加到最小生成树中}
}void testForKruskalMST()
{
    EdgeWeightGraph G("tinyEWG.txt");KruskalMST mst(G);queue<Edge>* q= mst.edges();while (!q->empty()) {
    out(q->front().toString()), hh;q->pop();}
}

工具

• 测试文件，头文件点这里 EdgeWeightGraph.h
• 并查集点这里