算法(第4版) Chapter 4.3 最小生成树

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


定义

  • 树是特殊的图

  • 图的生成树: 含有图全部顶点的无环连通子图

  • 加权无向图的最小生成树(MST):权重最小的生成树

约定

  • 只考虑连通图:根据生成树的定义

  • 边的权重可以为0或者为负

  • 所有边的权重各不相同:方便证明

原理

切分定理

  • 切分:将图的顶点集分为两个非空并且没有交集的集合

  • 横切边:链接两个属于不同集合的顶点的边。(下图的红色边)
     算法(第4版) Chapter 4.3 最小生成树

  • 在一副加权图中,给定任意的切分,它的横切边中的权重最小者必然属于图中的最小生成树

贪心算法

  • 将含有V个顶点的任意加权连通图中属于最小生成树的边标记为黑色。

  1. 初始状态下所有边均为灰色,找到一种切分,它产生的横切边均不为黑色。

  2. 将它权重最小的横切边标记为黑色。

  3. 反复,直到标记了V-1条黑色边为止。

加权无向图

加权边API

 算法(第4版) Chapter 4.3 最小生成树

  • 边的两个顶点

  • 权重

  • 权重大小比较

Edge 代码

public class Edge implements Comparable<Edge> {
    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

 算法(第4版) Chapter 4.3 最小生成树

  • 修改了方法 Iterable<Edge> adj(v) 原来返回的是相连的点,现在返回的是邻边

  • 新增了方法 Iterable<Edge> edges() 因为最小生成树更看重边的要素

EdgeWeightedGraph 代码

  • API允许平行边和自环,但是下面代码在实现的过程中并没有统计它们,这对最小生成树并不会产生影响。

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

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

    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<Edge> adj(int v) {
        return adj[v];
    }

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

最小生成树API

 算法(第4版) Chapter 4.3 最小生成树

Prim算法

  • 从点的方面考虑构建一颗MST

  • 设图G顶点集合为U,

  1. 任意选择图G中的一点作为起始点a,将该点加入集合V

  2. 再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小,此时将b点也加入集合V

  3. 以此类推,直至所有顶点全部被加入V,此时就构建出了一颗MST。

  • 因为有N个顶点,所以该MST就有N-1条边,每一次向集合V中加入一个点,就意味着找到一条MST的边。

数据结构

  • 顶点: 使用boolean marked[]。如果顶点v在树中,则marked[v]=true。

  • 边: 使用队列来保存最小生成树的边 or 由顶点索引的数组edgeTo[]

  • 横切边: 使用优先队列MinPQ<Edge>来根据权重进行比较

延时Prim图示

  • 将每一条和树相连的边加入优先队列MinPQ<Edge>,依次取出最小的边,取出后再判断是否是横切边
     算法(第4版) Chapter 4.3 最小生成树

LazyPrimMST 代码

  • 复杂度

    • 时间:ElogE 最坏情况下,一次插入成本为~lgE,删除最小元素的成本为~2lgE,最多只能插入E条边,删去E条边。

    • 空间:E 优先队列中最多可能有E条边

public class LazyPrimMST {
    private boolean[] marked; // MST vertices
    private Queue<Edge> mst; // MST edges
    private MinPQ<Edge> pq; // crossing (and ineligible) edges 横切边

    public LazyPrimMST(EdgeWeightedGraph G) {
        pq = new MinPQ<Edge>();
        marked = new boolean[G.V()];
        mst = new Queue<Edge>();
        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<Edge> edges()
    { return mst; }

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

即时Prim图示

  • 将每个点和树相连的最小边维护在数组edgeTo[] 和 distTo[]里,每向树加入一个点,更新一次数组

  • edgeTo[] 记录顶点/边; distTo[] 记录权重
     算法(第4版) Chapter 4.3 最小生成树

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<Double> 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<Double>(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<Edge> edges() // See Exercise 4.3.21.

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

Kruskal算法

  • 按照边的权重顺序(从小到大)处理

  1. 选择最小权重的边,判断是否会构成环,不会则加入最小生成树。

  2. 循环如此,直至树中含有V-1条边为止。

Kruskal算法图示

 算法(第4版) Chapter 4.3 最小生成树

KruskalMST 代码

  • 复杂度

    • 时间:ElogE 初始化优先队列,最坏情况E次比较;每次操作成本2lgE次比较,最多还会多E次connected() 和 V次union()操作,但这些成本相比ElogE的增长数量级可忽略不计(详见1.5)

    • 空间:E

public class KruskalMST {
    private Queue<Edge> mst;

    public KruskalMST(EdgeWeightedGraph G) {
        mst = new Queue<Edge>();
        MinPQ<Edge> pq = new MinPQ<Edge>(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<Edge> edges(){
        return mst; 
    }

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