关于最小生成树（MST）的三个小问题

Posted on | In | Visitors:

Cousera 《Algorithms II》课程作业

Minimum Spanning Tree (MST) 生成树为包含图所有顶点的无环连通子图，树中所有边的权值之和最小的生成树即为最小生成树（MST)。

MST Assignment

1、三个问题

Q1. Bottleneck minimum spanning tree - 最小瓶颈生成树

一个生成树的瓶颈容量为最大边的权重。最小瓶颈生成树 即为瓶颈容量最小的生成树。设计一个寻找最小瓶颈生成树的算法。

A: MST 一定是最小瓶颈生成树，即最小生成树是最小瓶颈生成树的充分不必要条件，因此用 prim 算法或 kruskal 算法即可获得。Coding 可见 algs4 中的 PrimMST.java & KruskalMST.java

Q2. Is an edge in a MST? - 一条边是否在 MST 内？

判断一条边是否是 MST 中的边。设计一个线性复杂度的算法。

A: 线性复杂度则不能通过寻找 MST 的方法。可以通过参考资料中的算法，边 e 两端的顶点分别为 u，v。删除边 e，寻找是否有由权重小于等于 e 的边组成的路径使得 uv 连通。具体代码如下，这里用到了 algs4 中的 Edge 类和 EdgeWeightedGraph 类等。

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
public class IsEInMST {
    private boolean[] marked;
    private double weightE;
    private int v, w; // vertexs of the given edge e;
    public IsEInMST(EdgeWeightedGraph G, Edge e) {
        marked = new boolean[G.V()];
        weightE = e.weight();
        v = e.either();
        w = e.other(v);
        dfs(G, v);
    }

    public boolean inMST() {
        return !marked[w];
    }

    private void dfs(EdgeWeightedGraph G, int v) {
        marked[v] = true;
        if (marked[w]) return;
        for (Edge e : G.adj(v)) {
            if(e.weight() < weightE && !marked[e.other(v)]) {
                dfs(G, e.other(v));
            }
        }
    }
}

参考资料：

Q3. Minimum-weight feedback edge set - 最小权重反馈边集

反馈边集合是指包含无向图中每一个环的至少一条边的集合。如果从图中移除反馈边集，得到的图无环。设计一个算法找到最小权重的反馈边集（假设所有边的权重为正）。

A: 即求解图最大生成树，对最大生成树所在边求补集即为最小权重反馈边集。通过调整最小堆为最大堆，利用 Prim 算法或 Kruskal 算法均可以实现。具体代码如下：

MinFeedbackEdgeSet 类用于调用最大生成树算法和返回集合结果
PrimMaxST 类为求解最大生成树的 Prim 版本，将优先索引队列改为最大堆实现
KruskalMaxST 类为求解最大生成树的 Kruskal 版本，将优先队列改为最大堆实现

MinFeedbackEdgeSet.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class MinFeedbackEdgeSet {
    private HashSet<Edge> minFeedbackEdgeSet;
    public MinFeedbackEdgeSet(EdgeWeightedGraph G) {
        minFeedbackEdgeSet = new HashSet<>();
        for (Edge e : G.edges()) {
            minFeedbackEdgeSet.add(e);
        }
        PrimMaxST maxST = new PrimMaxST(G); // or KruskalMaxST
        for (Edge e : maxST.edges()) {
            minFeedbackEdgeSet.remove(e);
        }
    }

    // return Set
    public Set<Edge> getMinFeedbackEdgeSet() {
        return minFeedbackEdgeSet;
    }
}

PrimMaxST.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
53
54
55
56
57
58
59
60

public class PrimMaxST {
    private Edge[] edgeTo; // edgeTo[v] = largest edge from tree vertex to non-tree vertex
    private double[] distTo; // distTo[v] = weight of largest such edge
    private boolean[] marked; // mark[v] = true if v on tree
    private IndexMaxPQ<Double> pq;

    public PrimMaxST(EdgeWeightedGraph G) {
        edgeTo = new Edge[G.V()];
        distTo = new double[G.V()];
        marked = new boolean[G.V()];
        pq = new IndexMaxPQ<>(G.V());
        for (int v = 0 ; v < G.V(); v++)
            distTo[v] = Double.NEGATIVE_INFINITY;

        for (int v= 0; v < G.V(); v++)
            if (!marked[v]) prim(G, v);
    }

    private void prim(EdgeWeightedGraph G, int s) {
        distTo[s] = 0.0;
        pq.insert(s, distTo[s]);
        while(!pq.isEmpty()) {
            int v = pq.delMax();
            scan(G, v);
        }
    }

    private void scan(EdgeWeightedGraph G, int v) {
        marked[v] = true;
        for (Edge e : G.adj(v)) {
            int w = e.other(v);
            if (marked[w]) continue;
            if (e.weight() > distTo[w]) {
                distTo[w] = e.weight();
                edgeTo[w] = e;
                if (pq.contains(w)) pq.increaseKey(w, distTo[w]); // update distance
                else pq.insert(w, distTo[w]);
            }
        }
    }

    public Iterable<Edge> edges() {
        Queue<Edge> maxST = new Queue<>();
        for (int v = 0; v < edgeTo.length; v++) {
            Edge e = edgeTo[v];
            if (e != null) {
                maxST.enqueue(e);
            }
        }
        return maxST;
    }

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

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

public class KruskalMaxST {
    private double weight; // weight of MaxST
    private Queue<Edge> maxST = new Queue<>(); // edges in MaxST

    public KruskalMaxST(EdgeWeightedGraph G) {
        MaxPQ<Edge> pq = new MaxPQ<>();
        for (Edge e : G.edges()) {
            pq.insert(e);
        }

        // greedy algorithm, need to use union-find to union all the forests
        UF uf = new UF(G.V());
        while (!pq.isEmpty() && maxST.size() < G.V() - 1) {
            Edge e = pq.delMax();
            int v = e.either(), w = e.other(v);
            if (!uf.connected(v, w)) {
                uf.union(v, w);
                maxST.enqueue(e);
                weight += e.weight();
            }
        }
    }

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

    public double getWeight() { return weight;};

}

2、总结

  • 回顾 IndexMinPQ 的实现方法，用两个数组关联 index 和 key 的位置
  • 回顾 Prim 算法，分为两种，lazy 型的只用一个优先队列即可，添加所有的边。时间复杂度 O()；egar 型的实时更新，只保留最小边和其权重。
  • 回顾 Kruskal 算法，需要利用查并集。
  • 学习图论的一些知识
  • 奇奇怪怪的知识又增加了