Java實現(xiàn)最小生成樹算法詳解

更新時間：2022年04月07日 08:19:29 作者：之一Yo

這篇文章主要介紹了如何在Java中實現(xiàn)最小生成樹算法，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Java有一定幫助，需要的可以參考一下

定義

在一幅無向圖G=(V,E) 中，(u,v) 為連接頂點u和頂點v的邊，w(u,v)為邊的權(quán)重，若存在邊的子集T⊆E且(V,T) 為樹，使得

最小，這稱 T 為圖 G 的最小生成樹。

說的通俗點，最小生成樹就是帶權(quán)無向圖中權(quán)值和最小的樹。下圖中黑色邊所標(biāo)識的就是一棵最小生成樹（圖片來自《算法第四版》），對于權(quán)值各不相同的連通圖來說最小生成樹只會有一棵：

帶權(quán)圖的實現(xiàn)

在《如何在 Java 中實現(xiàn)無向圖》中我們使用鄰接表數(shù)組實現(xiàn)了無向圖，其中鄰接表上的每個節(jié)點的數(shù)據(jù)域只是一個整數(shù)，代表著一個頂點。為了方便最小生成樹的迭代，我們將數(shù)據(jù)域換成 Edge 實例。Edge 有三個成員：頂點 v、頂點 w 和權(quán)重 weight，為了比較每一條邊的權(quán)重，需要實現(xiàn) Comparable 接口。代碼如下所示：

package com.zhiyiyo.graph;

/**
 * 圖中的邊
 */
public class Edge implements Comparable<Edge> {
    private final int v, w;
    private final double weight;

    public Edge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    /**
     * 返回邊中的一個頂點
     */
    int either() {
        return v;
    }

    /**
     * 返回邊中的拎一個頂點
     *
     * @param v 頂點 v
     * @return 另一個頂點
     */
    int another(int v) {
        if (this.v == v) {
            return w;
        } else if (w == v) {
            return this.v;
        } else {
            throw new RuntimeException("邊中不存在該頂點");
        }
    }

    public double getWeight() {
        return weight;
    }

    @Override
    public String toString() {
        return String.format("Edge{%d-%d %f}", v, w, weight);
    }

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

之后只要照貓畫虎，將 LinkGraph 的泛型從 Integer 換成 Edge 就行了：

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.stack.LinkStack;
import com.zhiyiyo.collection.stack.Stack;

/**
 * 帶權(quán)無向圖
 */
public class WeightedGraph {
    private final int V;
    protected int E;
    protected LinkStack<Edge>[] adj;

    public WeightedGraph(int V) {
        this.V = V;
        adj = (LinkStack<Edge>[]) new LinkStack[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new LinkStack<>();
        }
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

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

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

    /**
     * 獲取所有邊
     */
    public Iterable<Edge> edges() {
        Stack<Edge> edges = new LinkStack<>();
        for (int v = 0; v < V; ++v) {
            for (Edge edge : adj(v)) {
                if (edge.another(v) > v) {
                    edges.push(edge);
                }
            }
        }

        return edges;
    }
}

同時給出最小生成樹的 API：

package com.zhiyiyo.graph;

/**
 * 最小生成樹
 */
public interface MST {
    /**
     * 獲取最小生成樹中的所有邊
     */
    Iterable<Edge> edges();

    /**
     * 獲取最小生成樹的權(quán)重
     */
    double weight();
}

Kruskal 算法

假設(shè) E 是圖 G 中所有邊的集合，T 是最小生成樹的邊集合，kruskal 算法的思想是每次從 E 中彈出權(quán)值最小的邊 e_m，如果 e_m 不會和 T 中的邊構(gòu)成環(huán)，就將其加入 T 中，直到 |T|=|V|−1 也就是 TT 中邊的個數(shù)是圖 G 的頂點個數(shù) -1 時，就得到了最小生成樹。

對于上一幅圖，使用 kruskal 算法得到最小生成樹的過程如下圖所示：

首先將 E 中最小的邊 0-7 彈出并加到 T 中，此時的 EE 中最小邊為 2-3，雖然 2-3 和 0-7 無法構(gòu)成連通圖，但是沒關(guān)系，只要貪心地將其加入 T 中即可，因為后續(xù)其他邊的添加總會將二者連通起來。接著按照權(quán)值的升序依次把邊 1-7、0-2、5-7 加到 T 中，直到碰到邊 1-3，如果把 1-3 加入 T 中，就會出現(xiàn)環(huán) 1-3-2-0-7-1，所以直接將 1-3 舍棄，1-5、2-7 也同理被丟棄掉。由于邊 4-5 不會在 T 中構(gòu)成環(huán)，所以將其加入 T。重復(fù)上述步驟，直到|T|=|V|−1。

上述過程中有兩個影響性能的地方，一個是找出 E 中權(quán)值最小的邊 e_m，一個是判斷將 e_m 加到 T 中是否會出現(xiàn)環(huán)。

二叉堆

二叉堆是一棵完全二叉樹，且每個父節(jié)點總是大于等于（最大堆）或者小于等于（最小堆）他的子節(jié)點?！端惴ǖ谒陌妗分薪o出了使用數(shù)組存儲的最大堆的結(jié)構(gòu)，其中數(shù)組下標(biāo)為 0 的地方不存儲元素，假設(shè)下標(biāo)為 i 出存放的是父節(jié)點，那么 2i 和 2i+1 處就是子節(jié)點：

由于最小堆的堆頂節(jié)點總是最小的，所以只需將 E 變?yōu)橐粋€最小堆，每次取出堆頂?shù)脑丶纯?，時間復(fù)雜度為O(log?N)。下面來看下如何實現(xiàn)最小堆。

API

對于一個二叉堆，我們關(guān)心以下操作：

package com.zhiyiyo.collection.queue;

public interface PriorQueue<T extends Comparable<T>> {
    /**
     * 向堆中插入一個元素
     * @param item 插入的元素
     */
    void insert(T item);

    /**
     * 彈出堆頂?shù)脑?
     * @return 堆頂元素
     */
    T pop();

    /**
     * 獲取堆中的元素個數(shù)
     */
    int size();

    /**
     * 堆是否為空
     */
    boolean isEmpty();
}

插入

為了保證二叉堆是一棵完全二叉樹，每次都將新節(jié)點插到數(shù)組的末尾，也就是二叉樹的最后一個節(jié)點。如下圖所示，假設(shè)插入的節(jié)點為 A，它的父節(jié)點為 P，兄弟節(jié)點為 S，由于 P > A，這就打破了二叉堆的有序性，所以需要對堆進行調(diào)整。具體流程就是將兄弟節(jié)點中的較小者（A）選為父節(jié)點，而先前的父節(jié)點 P 則退位變?yōu)樽庸?jié)點。如果此時 A 的父節(jié)點小于 A，則無需繼續(xù)調(diào)整。但是下圖中只交換了 A、P 之后還是沒將二叉樹調(diào)整為堆有序狀態(tài)，因為父節(jié)點 D > A，接著將兄弟節(jié)點中較小的 A 變?yōu)楦腹?jié)點，而 D 則變成 A 的子節(jié)點，至此完成最小堆的調(diào)整。

上述過程的代碼如下所示，為了保證后續(xù)插入操作，每當(dāng)數(shù)組滿員時就對其進行擴容操作：

package com.zhiyiyo.collection.queue;

import java.util.Arrays;

public class MinPriorQueue<T extends Comparable<T>> implements PriorQueue<T>{
    private T[] array;
    private int N;

    public MinPriorQueue() {
        this(3);
    }

    public MinPriorQueue(int maxSize) {
        array = (T[]) new Comparable[maxSize + 1];
    }

    @Override
    public boolean isEmpty() {
        return N == 0;
    }

    @Override
    public int size() {
        return N;
    }

    @Override
    public void insert(T item) {
        array[++N] = item;
        swim(N);
        if (N == array.length - 1) resize(1 + 2 * N);
    }

    /**
     * 元素上浮
     *
     * @param k 元素的索引
     */
    private void swim(int k) {
        while (k > 1 && less(k, k / 2)) {
            swap(k, k / 2);
            k /= 2;
        }
    }

    private void swap(int a, int b) {
        T tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    private boolean less(int a, int b) {
        return array[a].compareTo(array[b]) < 0;
    }

    private void resize(int size) {
        array = Arrays.copyOf(array, size);
    }
}

刪除最小元素

假設(shè)我們需要刪除下圖中的 A 元素，這時候就需要將 A 和最小堆的最后一個元素 P 交換位置，并將數(shù)組的最后一個元素置為 null，使得 A 的引用次數(shù)變?yōu)?0，能被垃圾回收機制自動回收掉。交換之后最小堆的有序性被破壞了，因為父節(jié)點 P > 子節(jié)點 D，這時候和插入元素的操作一樣，將較小的子節(jié)點和父節(jié)點交換位置，使得較大的父節(jié)點能夠下沉，而較小的子節(jié)點上位，這個過程持續(xù)到?jīng)]有子節(jié)點被 P 更小為止。

實現(xiàn)代碼如下：

@Override
public T pop() {
    T item = array[1];
    swap(1, N);
    array[N--] = null;
    sink(1);
    if (N < (array.length - 1) / 4) resize((array.length - 1) / 2);
    return item;
}

/**
 * 元素下沉
 *
 * @param k 元素的索引
 */
private void sink(int k) {
    while (2 * k <= N) {
        int j = 2 * k;
        // 檢查是否有兩個子節(jié)點
        if (j < N && less(j + 1, j)) j++;
        if (less(k, j)) break;
        swap(k, j);
        k = j;
    }
}

并查集

假設(shè) TT 中的頂點的集合為 V′，則有圖 G′=(V′,T)。我們可以將 G′ 劃分為 n 個連通分量，每個連通分量有一個標(biāo)識 id∈[0,n−1]。要想判斷將邊 e_m 加入 T 后是否會構(gòu)成環(huán)，只需判斷 e_m 的兩個頂點是都屬于同一個連通分量即可。

判斷是否連通

由于每個連通分量都不存在環(huán)，可以看作一棵小樹，所以可以用一個數(shù)組 int[] ids 的索引表示樹中的節(jié)點（圖中的頂點），而索引處的元素值為父節(jié)點的索引值，數(shù)組中 ids[i] == i 的位置就是每棵樹的根節(jié)點，i 就是這個連通分量的標(biāo)識。而我們想要知道兩個節(jié)點之間是否連通，只需判斷他們所屬的樹的根節(jié)點是否相同即可。

假設(shè)從樹底的葉節(jié)點 6 出發(fā)，一路向上直到樹頂 1，中間需要經(jīng)過 5 和 0 兩個節(jié)點，如果節(jié)點 6 的根節(jié)點查詢得比較頻繁，那么這種查找效率是比較低的。由于我們只需知道根節(jié)點是誰即可，樹的結(jié)構(gòu)無關(guān)緊要，那么為何不想個辦法把節(jié)點 5、6 直接掛到根節(jié)點 1，這樣只要一步就能知道根節(jié)點。實現(xiàn)這種想法的的方式就是路徑壓縮：當(dāng)從節(jié)點 6 走到父節(jié)點 5 時，就將節(jié)點 6 掛到節(jié)點 5 的父節(jié)點 0 上；而從節(jié)點 0 走到根節(jié)點 1 時，就將子節(jié)點 6 和 5 掛到根節(jié)點 1 下，樹高被壓縮為 1。

實現(xiàn)上述過程的代碼如下所示：

package com.zhiyiyo.collection.tree;

public class UnionFind {
    private int[] ids;
    private int[] ranks;	// 每棵樹的高度
    private int N;			// 樹的數(shù)量

    public UnionFind(int N) {
        this.N = N;
        ids = new int[N];
        ranks = new int[N];
        for (int i = 0; i < N; i++) {
            ids[i] = i;
            ranks[i] = 1;
        }
    }

    /**
     * 獲取連通分量個數(shù)
     *
     * @return 連通分量個數(shù)
     */
    public int count() {
        return N;
    }

    /**
     * 獲得連通分量的 id
     *
     * @param p 觸點 id
     * @return 連通分量 id
     */
    public int find(int p) {
        while (p != ids[p]) {
            ids[p] = ids[ids[p]];   // 路徑壓縮
            p = ids[p];
        }
        return p;
    }

    /**
     * 判斷兩個觸點是否連通
     *
     * @param p 觸點 p 的 id
     * @param q 觸點 q 的 id
     * @return 是否連通
     */
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}

合并連通分量

我們將 E 中的 e_m 添加到T中時，e_m 的兩個節(jié)點肯定分屬于兩個連通分量，加入 T 之后就需要將這兩個分量合并，也就是將兩棵小樹合并為一顆大樹。假設(shè)兩棵樹的高度分別為 h1 和 h2，如果直接將一顆樹的根節(jié)點接到另一棵樹的葉節(jié)點上，會導(dǎo)致新樹高度為 h1+h2，降低尋找根節(jié)點的效率。解決方式是按秩歸并，將矮樹的根節(jié)點接到高樹的根節(jié)點上，會出現(xiàn)兩種情況：

如果 h1≠h2，新樹高度會是 max{h1,h2}m
如果 h1=h2=c，新樹高度會是 c+1

上述過程的代碼如下所示：

/**
 * 如果兩個觸點不處于同一個連通分量中，則連接兩個觸點
 *
 * @param p 觸點 p 的 id
 * @param q 觸點 q 的 id
 */
public void union(int p, int q) {
    int pId = find(p);
    int qId = find(q);
    if (qId == pId) return;

    // 將小樹并到大樹
    if (ranks[qId] > ranks[pId]) {
        ids[pId] = qId;
    } else if (ranks[qId] < ranks[pId]) {
        ids[qId] = pId;
    } else {
        ids[qId] = pId;
        ranks[pId]++;
    }

    N--;
}

實現(xiàn)算法

實現(xiàn) kruskal 算法時，先將所有邊加入最小堆中，每次取出堆頂?shù)脑?e_m，然后使用并查集判斷邊的兩個頂點是否連通，如果不連通就將 e_m 加入 T，重復(fù)這個過程直至 |T|=|V|−1，時間復(fù)雜度為O(|E|log?|E|)。

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.queue.LinkQueue;
import com.zhiyiyo.collection.queue.MinPriorQueue;
import com.zhiyiyo.collection.queue.Queue;
import com.zhiyiyo.collection.tree.UnionFind;

import java.util.stream.Stream;
import java.util.stream.StreamSupport;


public class KruskalMST implements MST {
    private Queue<Edge> mst;

    public KruskalMST(WeightedGraph graph) {
        mst = new LinkQueue<>();
        UnionFind uf = new UnionFind(graph.V());

        MinPriorQueue<Edge> pq = new MinPriorQueue<>();
        for (Edge e : graph.edges()) {
            pq.insert(e);
        }

        while (mst.size() < graph.V() - 1 && !pq.isEmpty()) {
            Edge edge = pq.pop();
            int v = edge.either();
            int w = edge.another(v);
            if (!uf.isConnected(v, w)) {
                mst.enqueue(edge);
                uf.union(v, w);
            }
        }
    }

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

    @Override
    public double weight() {
        Stream<Edge> stream = StreamSupport.stream(mst.spliterator(), false);
        return stream.map(Edge::getWeight).reduce(0d, Double::sum);
    }
}

Prim 算法

Prim 算法的思想是初始化最小生成樹為一個根節(jié)點 0，然后將根節(jié)點的所有鄰邊加入最小堆中，從最小堆中彈出最小的邊 e_m，如果 e_m 不會使得樹中出現(xiàn)環(huán)，將將其并入樹中。每當(dāng)有新的節(jié)點 v 被并入樹中時，就得將 v 的所有鄰邊加入最小堆中。重復(fù)上述過程直到 |T|=|V|−1，時間復(fù)雜度為O(|E|log?|E|)。代碼如下所示：

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.queue.LinkQueue;
import com.zhiyiyo.collection.queue.MinPriorQueue;
import com.zhiyiyo.collection.queue.Queue;

import java.util.stream.Stream;
import java.util.stream.StreamSupport;

/**
 * 延時版本 Prim 算法
 */
public class PrimMST implements MST {
    private boolean[] marked;
    private MinPriorQueue<Edge> pq;
    private Queue<Edge> mst;

    public LazyPrimMST(WeightedGraph graph) {
        marked = new boolean[graph.V()];
        pq = new MinPriorQueue<>();
        mst = new LinkQueue<>();

        mark(graph, 0);
        while (mst.size() < graph.V() - 1 && !pq.isEmpty()) {
            Edge edge = pq.pop();
            int v = edge.either();
            int w = edge.another(v);

            // 構(gòu)成環(huán)則舍棄
            if (marked[v] && marked[w]) continue;
            mst.enqueue(edge);

            if (!marked[v]) mark(graph, v);
            else if (!marked[w]) mark(graph, w);
        }
    }

    private void mark(WeightedGraph graph, int v) {
        marked[v] = true;
        for (Edge edge : graph.adj(v)) {
            if (!marked[edge.another(v)]) {
                pq.insert(edge);
            }
        }
    }

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

    @Override
    public double weight() {
        Stream<Edge> stream = StreamSupport.stream(mst.spliterator(), false);
        return stream.map(Edge::getWeight).reduce(0d, Double::sum);
    }
}

由于每次都是把新節(jié)點的所有鄰邊都加到了最小堆中，會引入許多無用的邊，所以《算法第四版》中給出了使用索引優(yōu)先隊列實現(xiàn)的即時版 Prim 算法，時間復(fù)雜度能達到O(|E|log?|V|)，但是這里寫不下了，大家可以自行查閱，以上~~

以上就是Java實現(xiàn)最小生成樹算法詳解的詳細(xì)內(nèi)容，更多關(guān)于Java最小生成樹的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: