快要一整個(gè)月沒(méi)有更新博客了，之前的幾周每周都想著要寫(xiě)狰域，但是最后時(shí)間還是排不開(kāi)，最近的狀態(tài)是一直在寫(xiě)代碼黄橘，一直在懟工作的需求兆览，順便刷刷算法題，國(guó)慶則是沒(méi)心沒(méi)肺的玩了七八天塞关，時(shí)間這么一分?jǐn)偺剑瑢?xiě)博客的時(shí)間總是擠不出來(lái)，罪過(guò)罪過(guò)。

其實(shí)數(shù)據(jù)結(jié)構(gòu)的系列一直也沒(méi)有寫(xiě)到頭小压，之后還打算寫(xiě)一個(gè)Leetcode刷題系列线梗，最近刷的題越多，越是感嘆某些題目的解法精妙怠益。

今天就接著上個(gè)月的來(lái)講講最小生成樹(shù)的算法吧仪搔。

最小生成樹(shù)是一副連通加權(quán)無(wú)向圖中一棵權(quán)值最小的生成樹(shù)。最小生成樹(shù)其實(shí)是最小權(quán)重生成樹(shù)的簡(jiǎn)稱(chēng)蜻牢。

一個(gè)連通圖可能有多個(gè)生成樹(shù)烤咧。當(dāng)圖中的邊具有權(quán)值時(shí)，總會(huì)有一個(gè)生成樹(shù)的邊的權(quán)值之和小于或等于其他生成樹(shù)的邊的權(quán)值之和抢呆。廣義上而言煮嫌，對(duì)于非聯(lián)通無(wú)向圖來(lái)說(shuō)，它的每一連通分量同樣有最小生成樹(shù)镀娶。

以有線電視電纜的架設(shè)為例立膛，若只能沿著街道布線，則以街道為邊梯码，而路口為頂點(diǎn)宝泵，其中必然有意最小的生成樹(shù)能使布線成本最低。

簡(jiǎn)單點(diǎn)說(shuō)有幾個(gè)城市你要設(shè)計(jì)一個(gè)線路轩娶，這個(gè)線路能走完所有的這幾個(gè)城市儿奶，而且路程最短，這個(gè)線路就是最小生成樹(shù)的含義鳄抒。

所以從上面的例子可以看出來(lái)闯捎，最小生成樹(shù)這個(gè)算法，對(duì)于解決生活實(shí)際問(wèn)題许溅，是一個(gè)很重要的存在瓤鼻。下面我們看看最小生成樹(shù)的算法：

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

using namespace std;

// 使用優(yōu)化的Prim算法求圖的最小生成樹(shù)
template <typename Graph, typename Weight>
class PrimMST {
private:
    Graph &G;                         // 圖的引用
    IndexMinHeap<Weight> ipq;         // 最小索引堆，算法輔助數(shù)據(jù)結(jié)構(gòu)
    vector< Edge<Weight>* > edgeTo;   // 訪問(wèn)的點(diǎn)所對(duì)應(yīng)的邊贤重，算法輔助數(shù)據(jù)結(jié)構(gòu)
    bool* marked;                     // 標(biāo)記數(shù)組茬祷，在算法運(yùn)行過(guò)程中標(biāo)記節(jié)點(diǎn)i是否被訪問(wèn)
    vector< Edge<Weight> > mst;       // 最小生成樹(shù)所包含的所有邊
    Weight mstWeight;                 // 最小生成樹(shù)的權(quán)值

    // 訪問(wèn)節(jié)點(diǎn)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);
            // 如果另一個(gè)端點(diǎn)未被訪問(wèn)
            if ( !marked[w] ) {
                // 如果從沒(méi)有考慮過(guò)這個(gè)端點(diǎn)，直接將這個(gè)端點(diǎn)和與之相連的邊加入索引堆
                if ( !edgeTo[w] ) {
                    edgeTo[w] = e;
                    ipq.insert(w, e->wt());
                }
                // 如果曾經(jīng)考慮過(guò)這個(gè)端點(diǎn)并蝗，但現(xiàn)在的邊比之前的邊更短祭犯，則進(jìn)行替換
                else if ( e->wt() < edgeTo[w]->wt() ) {
                    edgeTo[w] = e;
                    ipq.change(w, e->wt());
                }
            }
        }
    }

public:
    // 構(gòu)造函數(shù)，使用Prim算法求圖的最小生成樹(shù)
    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() ) {
            // 使用最小索引堆找出已經(jīng)訪問(wèn)的邊中權(quán)值最小的邊
            // 最小索引堆中存儲(chǔ)的是點(diǎn)的索引滚停，通過(guò)點(diǎn)的索引找到相對(duì)應(yīng)的邊
            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++版本的最小生成樹(shù)Prim MST算法沃粗，其中我引進(jìn)了Edge這個(gè)類(lèi)的數(shù)據(jù)結(jié)構(gòu)：

#ifndef EDGE_H
#define EDGE_H

#include <iostream>
#include <cassert>

using namespace std;

// 邊
template <typename Weight>
class Edge {
private:
    int a, b;       // 邊的兩個(gè)端點(diǎn)
    Weight weight;  // 邊的權(quán)值

public:
    // 構(gòu)造函數(shù)
    Edge(int a, int b, Weight weight) {
        this->a = a;
        this->b = b;
        this->weight = weight;
    }

    // 空的構(gòu)造函數(shù)，所有的成員變量都取默認(rèn)值
    Edge() {}

    // 析構(gòu)函數(shù)
    ~Edge() {}

    int v() { return a; }  // 返回第一個(gè)頂點(diǎn)
    int w() { return b; }  // 返回第二個(gè)頂點(diǎn)
    Weight wt() { return weight; }  // 返回權(quán)值

    // 給定一個(gè)頂點(diǎn)键畴，返回另一個(gè)頂點(diǎn)
    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;
    }

    // 邊的大小比較最盅，是對(duì)邊的權(quán)值的大小比較
    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

接下來(lái)放上Java版本:

public class PrimMST<Weight extends Number & Comparable> {
    private WeightedGraph<Weight> G;        // 圖的引用
    private IndexMinHeap<Weight> ipq;       // 最小索引堆，算法輔助數(shù)據(jù)結(jié)構(gòu)
    private Edge<Weight>[] edgeTo;          // 訪問(wèn)的點(diǎn)所對(duì)應(yīng)的邊，算法輔助數(shù)據(jù)結(jié)構(gòu)
    private Vector<Edge<Weight>> mst;       // 標(biāo)記數(shù)組檩禾，在算法運(yùn)行過(guò)程中標(biāo)記節(jié)點(diǎn)i是否被訪問(wèn)
    private boolean[] marked;               // 最小生成樹(shù)所包含的所有邊
    private Number mstWeight;               // 最小生成樹(shù)的權(quán)值

    // 構(gòu)造函數(shù)挂签，使用Prim算法求圖的最小生成樹(shù)
    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()) {
            // 使用最小索引堆找出已經(jīng)訪問(wèn)的邊中權(quán)值最小的邊
            // 最小索引堆中存儲(chǔ)的是點(diǎn)的索引，通過(guò)點(diǎn)的索引找到相對(duì)應(yīng)的邊
            int v = ipq.extractMinIndex();
            assert (edgeTo[v] != null);
            mst.add(edgeTo[v]);
            visit(v);
        }

        // 計(jì)算最小生成樹(shù)的權(quán)值
        mstWeight = mst.elementAt(0).wt();
        for (int i = 1; i < mst.size(); i++) {
            mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
        }
    }

    // 訪問(wèn)節(jié)點(diǎn)v
    private void visit(int v) {
        assert (!marked[v]);
        marked[v] = true;

        // 將和節(jié)點(diǎn)v相連接的未訪問(wèn)的另一端點(diǎn)盼产，和與之相連接的邊饵婆，放入最小堆中
        for (Object item : G.adj(v)) {
            Edge<Weight> e = (Edge<Weight>)item;
            int w = e.other(v);
            // 如果邊的另一個(gè)端點(diǎn)未被訪問(wèn)
            if (!marked[w]) {
                // 如果從沒(méi)有考慮過(guò)這個(gè)端點(diǎn)，直接將這個(gè)端點(diǎn)和與之相連接的邊加入索引堆
                if (edgeTo[w] == null) {
                    edgeTo[w] = e;
                    ipq.insert(w, e.wt());
                }
                // 如果曾經(jīng)考慮過(guò)這個(gè)端點(diǎn)戏售，但現(xiàn)在的邊比之前考慮的邊更短侨核，則進(jìn)行替換
                else if (e.wt().compareTo(edgeTo[w].wt()) < 0) {
                    edgeTo[w] = e;
                    ipq.change(w, e.wt());
                }
            }
        }
    }

    // 返回最小生成樹(shù)的邊
    Vector<Edge<Weight>> mstEdges() {
        return mst;
    }

    // 返回最小生成樹(shù)的權(quán)值
    Number result() {
        return mstWeight;
    }

其中Edge的數(shù)據(jù)結(jié)構(gòu)如下:

// 邊
public class Edge <Weight extends Comparable> implements Comparable<Edge<Weight>> {
    private int a;          // 邊的兩個(gè)端點(diǎn)
    private int b;
    private Weight weight;  // 邊的權(quán)值

    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;
    }  // 返回第一個(gè)頂點(diǎn)

    public int w() {
        return b;
    }  // 返回第二個(gè)頂點(diǎn)

    public Weight wt() {
        return weight;
    } // 返回權(quán)值

    // 給定一個(gè)頂點(diǎn)，返回另一個(gè)頂點(diǎn)
    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 另一個(gè)邊
     * @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格式的測(cè)試用例灌灾，就能很輕易的測(cè)試出我們的最小生成樹(shù)是否合格搓译。