图论——最小生成树

Algorithm

阅读此篇之前，需要了解图论的基础知识。

最小生成树MST应用的领域十分广泛，它比普通的无向图（连通图）多了权重的属性，这就使最小生成树可以被用来评估成本最小化的问题。

一些约定：

  • 只考虑连通图。（树是连通的）
  • 边的权重不一定表示距离。（可以表示很多意义）
  • 边的权重可能为0，也可能为负。
  • 所有边的权重各不相同。（相同权重的边会导致出现不同的最小生成树，为了简化分析，故此约定。但算法的实现不影响相同权重的情况。）

原理

树的性质：

  • 连通树中任意两个顶点都会产生环。
  • 删除任意一条边都会得到两个独立的树。

切分定理

切分是将图的所有顶点分为两个非空且互不重叠的集合。
横切边是指一条连接两个属于不同集合顶点的边。
给定任意的切分，横切边中最小者必然属于最小生成树。

切分定理也可以理解为一种贪心算法。不断重复寻找最小的横切边从而生成最小生成树。

加权无向图

为了可以处理权重，我们在无向图的基础上，加入带有权重的边Edge来生成加权无向图EdgeWeightedGraph。

带有权重的边

Edge 带有权重的边Edge.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Edge implements Comparable<Edge> {

    private final int v;            //顶点之一
    private final int w;            //另一个顶点
    private final double 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");
    }

    @Override
    public int compareTo(Edge that) {
        return Double.compare(this.weight(), that.weight());
    }
}

实现加权无向图

只需修改Graph中的addEdge()和邻接表adj[]即可。

EdgeWeightedGraph 加权无向图EdgeWeightedGraph.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class EdgeWeightedGraph {
    ···
    private Bag<Edge>[] adj;

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

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

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

    public Iterable<Edge> edges() {
        Bag<Edge> bag = new Bag<>();
        for (int v = 0; v < V; v++)
            for (Edge edge : adj[v])
                if (edge.other(v) > v) bag.add(edge);//防止重复添加
        return bag;
    }
}

Prim算法

Prim算法的每一步都会为一颗生长的树添加一条边。这条边是由树中的顶点，与不在树中的顶点且权重最小的边构成。

数据结构

  • 顶点。通过marked[]标记是否已访问。
  • 边。用Queue队列或edgeTo[]数组保存边，其中edgeTo[v]为将v(不在树中)连接到树中的Edge对象。
  • 横切边。通过使用优先队列MinPQ<Edge>来根据权重返回最小的边。

优先队列

这里MinPQ<T>只是一种优先队列，提供deleteMin()删除返回最小项，insert(T item)插入新的项。

优先队列性能
  • 空间：E
  • 时间：logE

Prim延迟实现

延迟实现，指的是优先队列添加边时，先不检查是否有效（有效指是否已被访问、是否新添加的边权重更小），而是在deleteMin()时，再检查边的有效性。

LazyPrimMST Prim延迟算法LazyPrimMST.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class LazyPrimMST {
    private boolean[] marked;   //最小生成树的顶点
    private Queue<Edge> mst;    //最小生成树的边
    private MinPQ<Edge> pq;     //横切边（包括失效的边）,MinPQ为优先队列

    public LazyPrimMST(EdgeWeightedGraph G) {
        pq = new MinPQ<>();
        marked = new boolean[G.V()];
        mst = new Queue<>();

        visit(G, 0);
        while (!pq.isEmpty()) {
            Edge e = pq.delMin();                   //从pq中得到权重最小的边
            int v = e.either(), w = e.other(v);
            if (marked[v] && marked[w]) continue;   //跳过失效的边
            mst.enqueue(e);                         //将边添加到树中
            if (!marked[v]) visit(G, v);            //将顶点添加到树中
            if (!marked[w]) visit(G, w);
        }
    }


    private void visit(EdgeWeightedGraph G, int v) {
        //标记顶点v并将所有连接v和未被标记的边加入pq
        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() {
        double weight = 0.0;
        for (Edge e : edges())
            weight += e.weight();
        return weight;
    }
}

Prim延迟实现的性能：

  • 空间：E（最多只能添加E条边）
  • 时间：ElogE（对E条边进行删除插入操作）

Prim即时实现

其实我们每次在保存优先队列时，更关注权重最小的新的边，这样可以使新顶点w与树的距离更小，从而形成最小生成树。

与LazyPrimMST相比，将marked[]和mst[]替换为distTo[]和edgeTo[]。

  • 假设v不在树中，但是至少有一条边与树相连，将要添加。
  • distTo[v]：表示v与树的最短边的权重。
  • edgeTo[v]：表示v与树的最短边。
  • 所有像v这类顶点都被保存在索引优先队列IndexMinPQ<T>中，索引v关联的值即最短边权重。

关于索引优先队列：使用索引int来对应值的一种优先队列.
性能：空间：V ，时间：logV

LazyPrimMST Prim延迟算法LazyPrimMST.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class PrimMST {
    private Edge[] edgeTo;          //距离树最近的边
    private double[] distTo;        //distTo[w]=edgTo[w].weight()
    private boolean[] marked;       //如果v在树中，则为true。可以去除，用disTo[]是否等于Double.POSITIVE_INFINITY来判断
    private IndexMinPQ<Double> pq;  //有效的横切边

    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);   //用顶点0、权重0初始化pq
        while (!pq.isEmpty())
            visit(G, pq.delMin());
    }

    private void visit(EdgeWeightedGraph G, int v) {
        //将顶点v添加到树中，并更新数据
        marked[v] = true;
        for (Edge e : G.adj(v)) {
            int w = e.other(v);

            if (marked[w]) continue;    //v-w失效
            if (e.weight() < distTo[w]) {
                //连接w和树的最佳边变为e，更新数据
                edgeTo[w] = e;
                distTo[w] = e.weight();
                if (pq.contains(w)) pq.changeKey(w, distTo[w]);
                else pq.insert(w, distTo[w]);
            }
        }
    }

    public Iterable<Edge> edges() {
        Queue<Edge> edges = new Queue<>();
        for (Edge anEdgeTo : edgeTo)
            if (anEdgeTo != null)
                edges.enqueue(anEdgeTo);
        return edges;
    }

    public double weight() {
        double weight = 0.0;
        for (Edge e : edges())
            weight += e.weight();
        return weight;
    }
}

Prim即时实现的性能：

  • 空间：V（最多只能添加V个顶点）
  • 时间：ElogV（对E条边进行删除插入操作）

性能对比

相比较两种实现而言，在巨型稀疏图中，性能在时间上差不多（logE ~ logV），但是空间上即时实现的算法变为了常数因子V。

Kruskal算法

在MST中，贪心算法的另一种选择就是每次只添加所有边中权重最小的边。

Kruskal算法将边按照权重顺序处理。每条边都可以看作是一个树，然后逐个由森林合并成为一颗树，最终完成。

在合并的时候，需要检查树与树是否已经连接。这里我们选用WeightedQuickUnionUF算法，来检查即将合并的两个树的两个顶点是否已经在同一个树中（判断树与树是否已经连接）。

WeightedQuickUnionUF算法

是一种加权连接算法，可以用树的思想理解它，这里不做详细探讨，我会抽时间在别的篇章中介绍这一巧妙的算法。算法实现

它提供connected(int v,int w)来检查v和w是否连接。性能为 O(1)。

它提供union(int v,int w)来连接v和w两点。性能为 O(logV)，V为总顶点数目。

Kruskal实现

比Prim算法更简洁，理解起来也更容易。

KruskalMST Kruskal算法KruskalMST.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class KruskalMST {
    private Queue<Edge> mst;
    private double weight;

    public KruskalMST(EdgeWeightedGraph G) {
        weight = 0.0;
        mst = new Queue<>();
        MinPQ<Edge> pq = new MinPQ<>();
        for (Edge e : G.edges()) pq.insert(e);
        WeightedQuickUnionUF uf = new WeightedQuickUnionUF(G.V());
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.delMin();
            int v = e.either(), w = e.other(v);
            if (uf.connected(v, w)) continue;
            uf.union(v, w);
            mst.enqueue(e);
            weight += e.weight();
        }
    }

    public Iterable<Edge> edges() {
        return mst;
    }

    public double weight() {
        return weight;
    }
}

性能

  • 空间：E（最多添加E条最小权重的边）
  • 时间：ElogE（优先队列最多有E条边，每次操作最多2logE次比较）

参考文献：《算法导论》 《Algorithms, 4th Edition》

本文标题:图论——最小生成树

文章作者:

发布时间:2018-09-02, 18:10:21

最后更新:2020-09-12, 16:12:15

原始链接:http://yif-hong.github.io/2018/09/02/Graph-MST/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 原理
    1. 1.1. 切分定理
  2. 2. 加权无向图
    1. 2.1. 带有权重的边
    2. 2.2. 实现加权无向图
  3. 3. Prim算法
    1. 3.1. 数据结构
      1. 3.1.1. 优先队列
        1. 3.1.1.1. 优先队列性能
    2. 3.2. Prim延迟实现
      1. 3.2.1. Prim延迟实现的性能：
    3. 3.3. Prim即时实现
      1. 3.3.1. Prim即时实现的性能：
    4. 3.4. 性能对比
  4. 4. Kruskal算法
    1. 4.1. WeightedQuickUnionUF算法
    2. 4.2. Kruskal实现
    3. 4.3. 性能
|