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

asoren 發布于2019-08-14 17:16 / 1437人閱讀

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

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

定義

樹是特殊的圖

圖的生成樹：含有圖全部頂點的無環連通子圖

加權無向圖的最小生成樹（MST）：權重最小的生成樹

約定

只考慮連通圖：根據生成樹的定義

邊的權重可以為0或者為負

所有邊的權重各不相同：方便證明

原理 切分定理

切分：將圖的頂點集分為兩個非空并且沒有交集的集合

橫切邊：鏈接兩個屬于不同集合的頂點的邊。（下圖的紅色邊）

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

貪心算法

將含有V個頂點的任意加權連通圖中屬于最小生成樹的邊標記為黑色。

初始狀態下所有邊均為灰色，找到一種切分，它產生的橫切邊均不為黑色。

將它權重最小的橫切邊標記為黑色。

反復，直到標記了V-1條黑色邊為止。

加權無向圖 加權邊API

邊的兩個頂點

權重

權重大小比較

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);
    }
}

加權無向圖API

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

新增了方法 Iterable edges() 因為最小生成樹更看重邊的要素

EdgeWeightedGraph 代碼

API允許平行邊和自環，但是下面代碼在實現的過程中并沒有統計它們，這對最小生成樹并不會產生影響。

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) //保證不重復
                    b.add(e);
        return b;
    }
}

最小生成樹API

Prim算法

從點的方面考慮構建一顆MST

設圖G頂點集合為U，

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

再從集合U-V中找到另一點b使得點b到V中任意一點的權值最小，此時將b點也加入集合V

以此類推，直至所有頂點全部被加入V，此時就構建出了一顆MST。

因為有N個頂點，所以該MST就有N-1條邊，每一次向集合V中加入一個點，就意味著找到一條MST的邊。

數據結構

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

邊：使用隊列來保存最小生成樹的邊 or 由頂點索引的數組edgeTo[]

橫切邊：使用優先隊列MinPQ來根據權重進行比較

延時Prim圖示

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

LazyPrimMST 代碼

復雜度

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

空間：E 優先隊列中最多可能有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.
}

即時Prim圖示

將每個點和樹相連的最小邊維護在數組edgeTo[] 和 distTo[]里，每向樹加入一個點，更新一次數組

edgeTo[] 記錄頂點/邊； distTo[] 記錄權重

PrimMST 代碼

復雜度

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

空間：E 優先隊列中最多可能有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]) { // 是橫切邊，且權重更小，因此更新
                edgeTo[w] = e;
                distTo[w] = e.weight();
                if (pq.contains(w))    //頂點已存在，則修改
                    pq.change(w, distTo[w]); 
                else    //頂點第一次出現，則新建
                    pq.insert(w, distTo[w]);
            }
        }
    }

    public Iterable edges() // See Exercise 4.3.21.

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

Kruskal算法

按照邊的權重順序（從小到大）處理

選擇最小權重的邊，判斷是否會構成環，不會則加入最小生成樹。

循環如此，直至樹中含有V-1條邊為止。

Kruskal算法圖示

KruskalMST 代碼

復雜度

時間：ElogE 初始化優先隊列，最壞情況E次比較；每次操作成本2lgE次比較，最多還會多E次connected() 和 V次union()操作，但這些成本相比ElogE的增長數量級可忽略不計（詳見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.
}

云服務器 GPU云服務器最小生成樹算法最小代價生成樹算法最小生成樹python算法最小生成樹c++算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66525.html

算法（第4版） Chapter 4.2 強聯通性 Tarjan算法補充

摘要：在實際的測試中，算法的運行效率也比算法高左右。此外，該算法與求無向圖的雙連通分量割點橋的算法也有著很深的聯系。學習該算法，也有助于深入理解求雙連通分量的算法，兩者可以類比組合理解。固屬于同一連通分支。參考資料http://blog.csdn.net/acmmmm/a...https://www.byvoid.com/blog/s...http://blog.csdn.net/noth...

maybe_009 2019-08-14 17:13 評論0 收藏0
算法（第4版） Chapter 4 練習題答案

摘要：離心率計算題目釋義計算點的離心率，圖的直徑，半徑，中心計算圖的圍長定義點的離心率圖中任意一點，的離心率是圖中其他點到的所有最短路徑中最大值。圖的中心圖中離心率長度等于半徑的點。改動離心率計算，在遍歷中增加的賦值即可。離心率計算 4.1.16 The eccentricity of a vertex v is the the length of the shortest path fr...

13651657101 2019-08-14 17:13 評論0 收藏0
算法（第4版） Chapter 5.2 單詞查找樹

摘要：謝路云單詞查找樹查找所需要的單詞的時間和鍵的長度成正比查找未命中只需檢查若干個單詞單詞查找樹單詞查找樹基本性質每個鏈接對應一個字符每個結點可能有一個值有值，說明存在從根結點到這個結點的字符串。它的存在是為了簡化查詢。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Ch...

tigerZH 2019-08-14 17:17 評論0 收藏0
【圖論】最小生成樹

摘要：最小生成樹有兩種生成算法普里姆算法克魯斯克爾算法算法普利姆算法算法流程我的理解任選一個元素，作為起始點將起始點標記為，代表該點已經加入最小生成樹集合計算這個集合到未加入的各個點的距離選擇一個最小的距離點，加入集合，即標記為已訪問更新集合到其最小生成樹有兩種生成算法 Prim（普里姆算法） Kruskal（克魯斯克爾）算法 Prim 算法（普利姆算法）算法流程：（我的理解）...

?xiaoxiao, 2019-08-16 12:33 評論0 收藏0