资讯专栏INFORMATION COLUMN

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

asoren / 1239人阅读

摘要:算法图示代码复杂度时间初始化优先队列,最坏情况次比较每次操作成本次比较,最多还会多次和次操作,但这些成本相比的增长数量级可忽略不计详见空间

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.
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66525.html

相关文章

  • 算法4Chapter 4.2 强联通性 Tarjan算法补充

    摘要:在实际的测试中,算法的运行效率也比算法高左右。此外,该算法与求无向图的双连通分量割点桥的算法也有着很深的联系。学习该算法,也有助于深入理解求双连通分量的算法,两者可以类比组合理解。固属于同一连通分支。 参考资料http://blog.csdn.net/acmmmm/a...https://www.byvoid.com/blog/s...http://blog.csdn.net/noth...

    maybe_009 评论0 收藏0
  • 算法4Chapter 4 练习题 答案

    摘要:离心率计算题目释义计算点的离心率,图的直径,半径,中心计算图的围长定义点的离心率图中任意一点,的离心率是图中其他点到的所有最短路径中最大值。图的中心图中离心率长度等于半径的点。改动离心率计算,在遍历中增加的赋值即可。 离心率计算 4.1.16 The eccentricity of a vertex v is the the length of the shortest path fr...

    13651657101 评论0 收藏0
  • 算法4Chapter 5.2 单词查找

    摘要:谢路云单词查找树查找所需要的单词的时间和键的长度成正比查找未命中只需检查若干个单词单词查找树单词查找树基本性质每个链接对应一个字符每个结点可能有一个值有值,说明存在从根结点到这个结点的字符串。它的存在是为了简化查询。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Ch...

    tigerZH 评论0 收藏0
  • 爆锤数据结构(期末复习笔记)

    摘要:第五题为压轴题考了三叉霍夫曼树数据结构期末机考大致有道题,难度由浅入深,根据去年实际体验,大致人均题。最后一题会比较难,可能会遇到比较复杂的数据结构,机考过程中前四题全部后可以试一下。输入第一行为测试数据数。每组测试数据的输出占一行。 ...

    Lucky_Boy 评论0 收藏0
  • 【图论】最小生成

    摘要:最小生成树有两种生成算法普里姆算法克鲁斯克尔算法算法普利姆算法算法流程我的理解任选一个元素,作为起始点将起始点标记为,代表该点已经加入最小生成树集合计算这个集合到未加入的各个点的距离选择一个最小的距离点,加入集合,即标记为已访问更新集合到其 最小生成树有两种生成算法 Prim(普里姆算法) Kruskal(克鲁斯克尔)算法 Prim 算法(普利姆算法) 算法流程:(我的理解)...

    ?xiaoxiao, 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<