算法（第4版） Chapter 4.3 最小生成樹

asoren 發(fā)布于2019-08-14 17:16 / 1443人閱讀

摘要：算法圖示代碼復(fù)雜度時(shí)間初始化優(yōu)先隊(duì)列，最壞情況次比較每次操作成本次比較，最多還會(huì)多次和次操作，但這些成本相比的增長數(shù)量級(jí)可忽略不計(jì)詳見空間

Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 謝路云
Chapter 4 Section 3 最小生成樹

定義

樹是特殊的圖

圖的生成樹：含有圖全部頂點(diǎn)的無環(huán)連通子圖

加權(quán)無向圖的最小生成樹（MST）：權(quán)重最小的生成樹

約定

只考慮連通圖：根據(jù)生成樹的定義

邊的權(quán)重可以為0或者為負(fù)

所有邊的權(quán)重各不相同：方便證明

原理 切分定理

切分：將圖的頂點(diǎn)集分為兩個(gè)非空并且沒有交集的集合

橫切邊：鏈接兩個(gè)屬于不同集合的頂點(diǎn)的邊。（下圖的紅色邊）

在一副加權(quán)圖中，給定任意的切分，它的橫切邊中的權(quán)重最小者必然屬于圖中的最小生成樹。

貪心算法

將含有V個(gè)頂點(diǎn)的任意加權(quán)連通圖中屬于最小生成樹的邊標(biāo)記為黑色。

初始狀態(tài)下所有邊均為灰色，找到一種切分，它產(chǎn)生的橫切邊均不為黑色。

將它權(quán)重最小的橫切邊標(biāo)記為黑色。

反復(fù)，直到標(biāo)記了V-1條黑色邊為止。

加權(quán)無向圖 加權(quán)邊API

邊的兩個(gè)頂點(diǎn)

權(quán)重

權(quán)重大小比較

Edge 代碼

public class Edge implements Comparable {
    private final int v; // one vertex
    private final int w; // the other vertex
    private final double weight; // edge weight

    public Edge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    public double weight() {
        return weight;
    }

    public int either() {
        return v;
    }

    public int other(int vertex) {
        if (vertex == v)
            return w;
        else if (vertex == w)
            return v;
        else
            throw new RuntimeException("Inconsistent edge");
    }

    public int compareTo(Edge that) {
        if (this.weight() < that.weight())
            return -1;
        else if (this.weight() > that.weight())
            return +1;
        else
            return 0;
    }

    public String toString() {
        return String.format("%d-%d %.2f", v, w, weight);
    }
}

加權(quán)無向圖API

修改了方法 Iterable adj(v) 原來返回的是相連的點(diǎn)，現(xiàn)在返回的是鄰邊

新增了方法 Iterable edges() 因?yàn)樽钚∩蓸涓粗剡叺囊?/p>

EdgeWeightedGraph 代碼

API允許平行邊和自環(huán)，但是下面代碼在實(shí)現(xiàn)的過程中并沒有統(tǒng)計(jì)它們，這對最小生成樹并不會(huì)產(chǎn)生影響。

public class EdgeWeightedGraph {
    private final int V; // number of vertices
    private int E; // number of edges
    private Bag[] adj; // adjacency lists

    public EdgeWeightedGraph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag();
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public void addEdge(Edge e) {
        int v = e.either(), w = e.other(v);
        adj[v].add(e);
        adj[w].add(e);
        E++;
    }

    public Iterable adj(int v) {
        return adj[v];
    }

    public Iterable edges() {
        Bag b = new Bag();
        for (int v = 0; v < V; v++)
            for (Edge e : adj[v])
                if (e.other(v) > v) //保證不重復(fù)
                    b.add(e);
        return b;
    }
}

最小生成樹API

Prim算法

從點(diǎn)的方面考慮構(gòu)建一顆MST

設(shè)圖G頂點(diǎn)集合為U，

任意選擇圖G中的一點(diǎn)作為起始點(diǎn)a，將該點(diǎn)加入集合V

再從集合U-V中找到另一點(diǎn)b使得點(diǎn)b到V中任意一點(diǎn)的權(quán)值最小，此時(shí)將b點(diǎn)也加入集合V

以此類推，直至所有頂點(diǎn)全部被加入V，此時(shí)就構(gòu)建出了一顆MST。

因?yàn)橛蠳個(gè)頂點(diǎn)，所以該MST就有N-1條邊，每一次向集合V中加入一個(gè)點(diǎn)，就意味著找到一條MST的邊。

數(shù)據(jù)結(jié)構(gòu)

頂點(diǎn)：使用boolean marked[]。如果頂點(diǎn)v在樹中，則marked[v]=true。

邊：使用隊(duì)列來保存最小生成樹的邊 or 由頂點(diǎn)索引的數(shù)組edgeTo[]

橫切邊：使用優(yōu)先隊(duì)列MinPQ來根據(jù)權(quán)重進(jìn)行比較

延時(shí)Prim圖示

將每一條和樹相連的邊加入優(yōu)先隊(duì)列MinPQ，依次取出最小的邊，取出后再判斷是否是橫切邊

LazyPrimMST 代碼

復(fù)雜度

時(shí)間：ElogE 最壞情況下，一次插入成本為~lgE，刪除最小元素的成本為~2lgE，最多只能插入E條邊，刪去E條邊。

空間：E 優(yōu)先隊(duì)列中最多可能有E條邊

public class LazyPrimMST {
    private boolean[] marked; // MST vertices
    private Queue mst; // MST edges
    private MinPQ pq; // crossing (and ineligible) edges 橫切邊

    public LazyPrimMST(EdgeWeightedGraph G) {
        pq = new MinPQ();
        marked = new boolean[G.V()];
        mst = new Queue();
        visit(G, 0); // assumes G is connected (see Exercise 4.3.22)
        while (!pq.isEmpty()) {
            Edge e = pq.delMin(); // Get lowest-weight
            int v = e.either(), w = e.other(v); // edge from pq.
            if (marked[v] && marked[w])
                continue; // Skip if ineligible.
            mst.enqueue(e); // Add edge to tree.
            if (!marked[v])
                visit(G, v); // Add vertex to tree
            if (!marked[w])
                visit(G, w); // (either v or w).
        }
    }

    private void visit(EdgeWeightedGraph G, int v) { // Mark v and add to pq all edges from v unmarked vertices.
        marked[v] = true;
        for (Edge e : G.adj(v))
            if (!marked[e.other(v)])
                pq.insert(e);
    }

    public Iterable edges()
    { return mst; }

    public double weight() // See Exercise 4.3.31.
}

即時(shí)Prim圖示

將每個(gè)點(diǎn)和樹相連的最小邊維護(hù)在數(shù)組edgeTo[] 和 distTo[]里，每向樹加入一個(gè)點(diǎn)，更新一次數(shù)組

edgeTo[] 記錄頂點(diǎn)/邊； distTo[] 記錄權(quán)重

PrimMST 代碼

復(fù)雜度

時(shí)間：ElogV 最壞情況下，一次插入成本為~lgV，刪除最小元素的成本為~2lgV，最多只能插入E條邊，刪去E條邊。

空間：E 優(yōu)先隊(duì)列中最多可能有E條邊

public class PrimMST {
    private Edge[] edgeTo; // shortest edge from tree vertex
    private double[] distTo; // distTo[w] = edgeTo[w].weight()
    private boolean[] marked; // true if v on tree
    private IndexMinPQ pq; // eligible crossing edges 橫切邊

    public PrimMST(EdgeWeightedGraph G) {
        edgeTo = new Edge[G.V()];
        distTo = new double[G.V()];
        marked = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY; //初始化
        pq = new IndexMinPQ(G.V());
        distTo[0] = 0.0;
        pq.insert(0, 0.0); // Initialize pq with 0, weight 0.
        while (!pq.isEmpty())
            visit(G, pq.delMin()); // Add closest vertex to tree.
    }

    private void visit(EdgeWeightedGraph G, int v) { // Add v to tree; update data structures.
        marked[v] = true;
        for (Edge e : G.adj(v)) {
            int w = e.other(v);
            if (marked[w]) //v w都在樹里，不是橫切邊，因此不用更新
                continue; 
            if (e.weight() < distTo[w]) { // 是橫切邊，且權(quán)重更小，因此更新
                edgeTo[w] = e;
                distTo[w] = e.weight();
                if (pq.contains(w))    //頂點(diǎn)已存在，則修改
                    pq.change(w, distTo[w]); 
                else    //頂點(diǎn)第一次出現(xiàn)，則新建
                    pq.insert(w, distTo[w]);
            }
        }
    }

    public Iterable edges() // See Exercise 4.3.21.

    public double weight() // See Exercise 4.3.31.
}

Kruskal算法

按照邊的權(quán)重順序（從小到大）處理

選擇最小權(quán)重的邊，判斷是否會(huì)構(gòu)成環(huán)，不會(huì)則加入最小生成樹。

循環(huán)如此，直至樹中含有V-1條邊為止。

Kruskal算法圖示

KruskalMST 代碼

復(fù)雜度

時(shí)間：ElogE 初始化優(yōu)先隊(duì)列，最壞情況E次比較；每次操作成本2lgE次比較，最多還會(huì)多E次connected() 和 V次union()操作，但這些成本相比ElogE的增長數(shù)量級(jí)可忽略不計(jì)（詳見1.5）

空間：E

public class KruskalMST {
    private Queue mst;

    public KruskalMST(EdgeWeightedGraph G) {
        mst = new Queue();
        MinPQ pq = new MinPQ(G.edges());
        UF uf = new UF(G.V()); //Reference: Union Find in Chapter 1
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.delMin(); // Get min weight edge on pq
            int v = e.either(), w = e.other(v); // and its vertices.
            if (uf.connected(v, w))
                continue; // Ignore ineligible edges.
            uf.union(v, w); // Merge components.
            mst.enqueue(e); // Add edge to mst.
        }
    }

    public Iterable edges(){
        return mst; 
    }

    public double weight() // See Exercise 4.3.31.
}