数据结构——最小生成树(C++和Java实现)

快要一整个月没有更新博客了,之前的几周每周都想着要写,但是最后时间还是排不开,最近的状态是一直在写代码,一直在怼工作的需求,顺便刷刷算法题,国庆则是没心没肺的玩了七八天,时间这么一分摊,写博客的时间总是挤不出来,罪过罪过。

其实数据结构的系列一直也没有写到头,之后还打算写一个Leetcode刷题系列,最近刷的题越多,越是感叹某些题目的解法精妙。

今天就接着上个月的来讲讲最小生成树的算法吧。

最小生成树是一副连通加权无向图中一棵权值最小的生成树。最小生成树其实是最小权重生成树的简称。

一个连通图可能有多个生成树。当图中的边具有权值时,总会有一个生成树的边的权值之和小于或等于其他生成树的边的权值之和。广义上而言,对于非联通无向图来说,它的每一连通分量同样有最小生成树。

以有线电视电缆的架设为例,若只能沿着街道布线,则以街道为边,而路口为顶点,其中必然有意最小的生成树能使布线成本最低。

简单点说有几个城市你要设计一个线路,这个线路能走完所有的这几个城市,而且路程最短,这个线路就是最小生成树的含义。

所以从上面的例子可以看出来,最小生成树这个算法,对于解决生活实际问题,是一个很重要的存在。下面我们看看最小生成树的算法:

#include <iostream>
#include <vector>
#include <cassert>
#include "Edge.h"
#include "IndexMinHeap.h"

using namespace std;

// 使用优化的Prim算法求图的最小生成树
template <typename Graph, typename Weight>
class PrimMST {
private:
    Graph &G;                         // 图的引用
    IndexMinHeap<Weight> ipq;         // 最小索引堆,算法辅助数据结构
    vector< Edge<Weight>* > edgeTo;   // 访问的点所对应的边,算法辅助数据结构
    bool* marked;                     // 标记数组,在算法运行过程中标记节点i是否被访问
    vector< Edge<Weight> > mst;       // 最小生成树所包含的所有边
    Weight mstWeight;                 // 最小生成树的权值

    // 访问节点v
    void visit( int v ) {
        assert( !marked[v] );
        marked[v] = true;

        typename Graph::adjIterator adj(G, v);
        for (Edge<Weight>* e = adj.begin(); !adj.end(); e = adj.next()) {
            int w = e->other(v);
            // 如果另一个端点未被访问
            if ( !marked[w] ) {
                // 如果从没有考虑过这个端点,直接将这个端点和与之相连的边加入索引堆
                if ( !edgeTo[w] ) {
                    edgeTo[w] = e;
                    ipq.insert(w, e->wt());
                }
                // 如果曾经考虑过这个端点,但现在的边比之前的边更短,则进行替换
                else if ( e->wt() < edgeTo[w]->wt() ) {
                    edgeTo[w] = e;
                    ipq.change(w, e->wt());
                }
            }
        }
    }

public:
    // 构造函数,使用Prim算法求图的最小生成树
    PrimMST(Graph &graph):G(graph), ipq(IndexMinHeap<double>(graph.V())) {

        assert( graph.E() >= 1 );

        // 算法初始化
        marked = new bool[G.V()];
        for (int i = 0; i < G.V(); i++) {
            marked[i] = false;
            edgeTo.push_back(NULL);
        }
        mst.clear();

        // Prim
        visit(0);
        while( !ipq.isEmpty() ) {
            // 使用最小索引堆找出已经访问的边中权值最小的边
            // 最小索引堆中存储的是点的索引,通过点的索引找到相对应的边
            int v = ipq.extractMinIndex();
            assert ( edgeTo[v] );
            mst.push_back( *edgeTo[v] );
            visit( v );
        }

        mstWeight = mst[0].wt();
        for (int i = 1; i < mst.size(); i++) {
            mstWeight += mst[i].wt();
        }
    }

    ~PrimMST() {
        delete[] marked;
    }

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

    Weight result() {
        return mstWeight;
    }
};

上面的是C++版本的最小生成树Prim MST算法,其中我引进了Edge这个类的数据结构:

#ifndef EDGE_H
#define EDGE_H

#include <iostream>
#include <cassert>

using namespace std;

// 边
template <typename Weight>
class Edge {
private:
    int a, b;       // 边的两个端点
    Weight weight;  // 边的权值

public:
    // 构造函数
    Edge(int a, int b, Weight weight) {
        this->a = a;
        this->b = b;
        this->weight = weight;
    }

    // 空的构造函数,所有的成员变量都取默认值
    Edge() {}

    // 析构函数
    ~Edge() {}

    int v() { return a; }  // 返回第一个顶点
    int w() { return b; }  // 返回第二个顶点
    Weight wt() { return weight; }  // 返回权值

    // 给定一个顶点,返回另一个顶点
    int other( int x ) {
        assert( x == a || x == b);
        return x == a ? b : a;
    }

    // 输出边的信息
    friend ostream& operator<<(ostream &os, const Edge &e) {
        os << e.a << "-" << e.b << ": " << e.weight;
        return os;
    }

    // 边的大小比较,是对边的权值的大小比较
    bool operator<(Edge<Weight>& e) {
        return weight < e.wt();
    }

    bool operator<=(Edge<Weight>& e) {
        return weight <= e.wt();
    }

    bool operator>(Edge<Weight>& e) {
        return weight > e.wt();
    }

    bool operator>=(Edge<Weight>& e) {
        return weight >= e.wt();
    }

    bool operator==(Edge<Weight>& e) {
        return weight == e.wt();
    }
};

#endif //EDGE_H

接下来放上Java版本:

public class PrimMST<Weight extends Number & Comparable> {
    private WeightedGraph<Weight> G;        // 图的引用
    private IndexMinHeap<Weight> ipq;       // 最小索引堆,算法辅助数据结构
    private Edge<Weight>[] edgeTo;          // 访问的点所对应的边,算法辅助数据结构
    private Vector<Edge<Weight>> mst;       // 标记数组,在算法运行过程中标记节点i是否被访问
    private boolean[] marked;               // 最小生成树所包含的所有边
    private Number mstWeight;               // 最小生成树的权值

    // 构造函数,使用Prim算法求图的最小生成树
    public PrimMST(WeightedGraph graph) {
        G = graph;
        assert graph.E() >= 1;
        ipq = new IndexMinHeap<Weight>(graph.V());

        // 算法初始化
        marked = new boolean[G.V()];
        edgeTo = new Edge[G.V()];
        for (int i = 0; i < G.V(); i++) {
            marked[i] = false;
            edgeTo[i] = null;
        }
        mst = new Vector<Edge<Weight>>();

        // Prim
        visit(0);
        while (!ipq.isEmpty()) {
            // 使用最小索引堆找出已经访问的边中权值最小的边
            // 最小索引堆中存储的是点的索引,通过点的索引找到相对应的边
            int v = ipq.extractMinIndex();
            assert (edgeTo[v] != null);
            mst.add(edgeTo[v]);
            visit(v);
        }

        // 计算最小生成树的权值
        mstWeight = mst.elementAt(0).wt();
        for (int i = 1; i < mst.size(); i++) {
            mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
        }
    }

    // 访问节点v
    private void visit(int v) {
        assert (!marked[v]);
        marked[v] = true;

        // 将和节点v相连接的未访问的另一端点,和与之相连接的边,放入最小堆中
        for (Object item : G.adj(v)) {
            Edge<Weight> e = (Edge<Weight>)item;
            int w = e.other(v);
            // 如果边的另一个端点未被访问
            if (!marked[w]) {
                // 如果从没有考虑过这个端点,直接将这个端点和与之相连接的边加入索引堆
                if (edgeTo[w] == null) {
                    edgeTo[w] = e;
                    ipq.insert(w, e.wt());
                }
                // 如果曾经考虑过这个端点,但现在的边比之前考虑的边更短,则进行替换
                else if (e.wt().compareTo(edgeTo[w].wt()) < 0) {
                    edgeTo[w] = e;
                    ipq.change(w, e.wt());
                }
            }
        }
    }

    // 返回最小生成树的边
    Vector<Edge<Weight>> mstEdges() {
        return mst;
    }

    // 返回最小生成树的权值
    Number result() {
        return mstWeight;
    }

其中Edge的数据结构如下:

// 边
public class Edge <Weight extends Comparable> implements Comparable<Edge<Weight>> {
    private int a;          // 边的两个端点
    private int b;
    private Weight weight;  // 边的权值

    public Edge(int a, int b, Weight weight) {
        this.a = a;
        this.b = b;
        this.weight = weight;
    }

    public Edge(Edge<Weight> e) {
        this.a = e.a;
        this.b = e.b;
        this.weight = e.weight;
    }

    public int v() {
        return a;
    }  // 返回第一个顶点

    public int w() {
        return b;
    }  // 返回第二个顶点

    public Weight wt() {
        return weight;
    } // 返回权值

    // 给定一个顶点,返回另一个顶点
    public int other(int x) {
        assert (x == a || x == b);
        return x == a ? b : a;
    }

    /**
     * 输出边的信息
     * @return String
     */
    public String toString() {
        return "" + a + "-" + b + ": " + weight;
    }

    /**
     * 边之间的比较
     * @param that 另一个边
     * @return Int
     */
    public int compareTo(Edge that) {
        if (weight.compareTo(that.wt()) < 0) {
            return -1;
        } else if (weight.compareTo(that.wt()) > 0) {
            return +1;
        } else {
            return 0;
        }
    }
}

然后只要找到txt格式的测试用例,就能很轻易的测试出我们的最小生成树是否合格。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

2017.7.21夏令营清北学堂解题报告

预计分数: 60+30+0=90=划水 实际分数: 90+30+20=140=rank5=雷蛇鼠标 一句话总结:今天该买彩票! T1: 题目描述 从前有一个?...

28760
来自专栏华章科技

程序员必须知道的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,...

11720
来自专栏程序员互动联盟

程序员必须要掌握的十大经典算法

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

434130
来自专栏章鱼的慢慢技术路

Go指南练习_循环与函数

23720
来自专栏数据小魔方

求和函数系列——sum函数家族

今天要跟大家分享的是一组求和函数系列——sum函数家族! excel中最长用到的求和函数就是sum函数系列了,sum函数系列一共有三组函数: sum sumif...

29240
来自专栏CSDN技术头条

程序员必须知道的十大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较...

21150
来自专栏专注数据中心高性能网络技术研发

[LeetCode]Array主题系列{1,11,15,16,18,26,27,31,33,34题}

1.内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结...

34860
来自专栏CDA数据分析师

数据分析师不可不知的10大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

22280
来自专栏老九学堂

程序员必须知道的十大基础实用算法及讲解!

最近社群很多的小伙伴们对算法进行了激烈的讨论与学习,今天老九君就给大家介绍一些编程语言里的基础算法,提高小伙伴们的算法知识及编程里对算法的运用。 我们一起来看看...

36450
来自专栏CSDN技术头条

程序员都应该知道的10大算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。

12410

扫码关注云+社区

领取腾讯云代金券