我們已經(jīng)掌握了圖的概念和基本操作，接下來了解一下圖可以解決的問題。圖主要用來解決多對多問題，比如有多個(gè)起點(diǎn)和終點(diǎn)，或者有多種選擇的問題。例如我們要從下圖中找到能連通每個(gè)頂點(diǎn)的最短路徑，或者尋找從頂點(diǎn)v₀到頂點(diǎn)v₃的最短路徑：

網(wǎng)

現(xiàn)在我們要研究的就是尋找能連通每個(gè)頂點(diǎn)的最短路徑，我們稱這種構(gòu)造連通網(wǎng)的最小代價(jià)生成樹為最小生成樹。這個(gè)問題有兩個(gè)經(jīng)典的算法，分別是普里姆算法和克魯斯卡爾算法。

普里姆（Prim）算法

普里姆算法的思想是每次都從未選擇的頂點(diǎn)中選擇代價(jià)最小的頂點(diǎn)，并更新剩余頂點(diǎn)的最小代價(jià)值。我們以上圖為例，演示普里姆算法的過程。

首先選擇一個(gè)頂點(diǎn)，比如v₀，與v₀相連的頂點(diǎn)記它的最小代價(jià)值為實(shí)際值，其余頂點(diǎn)記為∞，如下所示：

選擇頂點(diǎn)v0

接下來選擇距離v₀最近的頂點(diǎn)v₁加入已選列表，并更新剩余結(jié)點(diǎn)到已選列表的距離值，如下所示：

選擇頂點(diǎn)v1

接下來再次選擇距離已選列表最近的頂點(diǎn)，很顯然v₅最近，選擇后結(jié)果如下：

選擇v5

按照同樣的方式，我們選擇v₈加入已選列表，如下所示：

選擇v8

重復(fù)這一操作，最后我們可以得到如下路徑，就是我們要構(gòu)造的最小生成樹：

最終結(jié)果

克魯斯卡爾（Kruskal）算法

普里姆算法是從頂點(diǎn)出發(fā)，我們也可以從邊出發(fā)，克魯斯卡爾算法就是每次選擇合適的最小的邊加入已選列表，直至所有頂點(diǎn)都連通。我們依然以上圖為例，演示它的過程。

因?yàn)橐獙呥M(jìn)行操作，所以首先應(yīng)該對所有的邊按照代價(jià)大小排序，還記得圖的邊集數(shù)組存儲方式嗎？我們把邊排序后就放在一個(gè)邊集數(shù)組中，如下所示：

邊集數(shù)組

首先，我們把每個(gè)頂點(diǎn)都看作一棵獨(dú)立的樹，這些頂點(diǎn)組成了一個(gè)森林，而我們的目的就是把這個(gè)森林組合成一棵樹，如下所示：

頂點(diǎn)組成的森林

第一步，我們從邊集數(shù)組中取最短的邊，將森林中的對應(yīng)頂點(diǎn)連接起來，第一個(gè)邊就是(v₄, v₇)，weight為7，如下所示：

連接v4和v7

頂點(diǎn)v₄和v₇現(xiàn)在就屬于同一棵樹了，接下來我們再找最短的邊，它的兩個(gè)就不能在同一棵樹上，第二條邊是(v₂, v₈)，如下所示：

連接v2和v8

按照同樣的步驟，我們繼續(xù)連接剩下的邊，直到連接完(v₃, v₇)如下：

連接v3和v7

接下來最短的邊是(v₅, v₆)，但是頂點(diǎn)v₅和v₆在同一棵樹上，如果把它們連起來，就會形成一個(gè)環(huán)，這明顯是不對的，所以這個(gè)邊是無效的。接下來的(v₁, v₂)同理，所以我們應(yīng)該連接(v₆, v₇)，如下所示：

連接v6和v7

至此，所有的頂點(diǎn)都連通了，可以看到，結(jié)果和普里姆算法是一致的。

代碼實(shí)現(xiàn)

普里姆算法

依然以鄰接矩陣為例，演示普里姆算法的實(shí)現(xiàn)過程，代碼如下所示：

public <T> void prim(AMGraph<T> graph) {
    int len = graph.getVertexNum();
    int min = 0;
    // 相關(guān)頂點(diǎn)的坐標(biāo)
    int[] adjvex = new int[len];
    // 最小代價(jià)
    int[] lowcost = new int[len];
    // 將位置0的頂點(diǎn)加入生成樹，設(shè)置lowcost為0
    lowcost[0] = 0;
    adjvex[0] = 0;

    for (int i = 1; i < len; i++) {
        // 和v0相連的頂點(diǎn)的權(quán)值存入數(shù)組
        lowcost[i] = graph.getWeight(0, i);
        // 全部坐標(biāo)都初始化為v0下標(biāo)
        adjvex[i] = 0;
    }

    for (int i = 1; i < len; i++) {
        // INFINITE是一個(gè)不可能的值，這里設(shè)置為Int的最大值
        min = INFINITE;
        int j = 1, k = 0;
        while (j < len) {
            // 循環(huán)剩下的全部頂點(diǎn)，尋找lowcoast
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }

        System.out.println("當(dāng)前頂點(diǎn)中最小權(quán)值的邊是：(" + adjvex[k] + ", " + k + ")" + "最小值為：" + min);

        // 把此頂點(diǎn)的權(quán)值設(shè)為0
        lowcost[k] = 0;
        for (j = 1; j < len; j++) {
            // 把當(dāng)前的k頂點(diǎn)加入已選列表，并更新剩余頂點(diǎn)的權(quán)值
            if (lowcost[j] != 0 && graph.getWeight(k, j) < lowcost[j]) {
                lowcost[j] = graph.getWeight(k, j);
                adjvex[j] = k;
            }
        }
    }
}

可以看到，因?yàn)殡p重for循環(huán)的原因，普里姆算法的時(shí)間復(fù)雜度為O(n²)。

克魯斯卡爾算法

public void kruskal(Edge[] edges) {
    int len = edges.length;
    // 定義一個(gè)數(shù)組，保存每個(gè)頂點(diǎn)的父結(jié)點(diǎn)，也就是它所在的樹結(jié)構(gòu)中的父結(jié)點(diǎn)
    int[] parent = new int[len];
    for (int i = 0; i < len; i++) {
        parent[i] = 0;
    }

    int begin,end;
    for (int i = 0; i < len; i++) {
        // begin頂點(diǎn)所在樹的根結(jié)點(diǎn)
        begin = find(parent,edges[i].getBegin());
        // end頂點(diǎn)所在樹的根結(jié)點(diǎn)
        end = find(parent,edges[i].getEnd());
        // 不在同一棵樹上
        if (end != begin){
            parent[end] = begin;
            System.out.println("加入邊：(" + edges[i].getBegin()+", "+edges[i].getEnd() +") , weight = "+edges[i].getWeight());
        }
    }
}

private int find(int[] parent, int find){
    // 找到這棵樹的根結(jié)點(diǎn)
    while (parent[find]>0){
        find = parent[find];
    }
    return find;
}

這里省略了把鄰接矩陣轉(zhuǎn)為邊集數(shù)組和對邊集數(shù)組進(jìn)行排序的代碼。可以看到，克魯斯卡爾算法的時(shí)間復(fù)雜度和邊的個(gè)數(shù)有關(guān)，記邊的個(gè)數(shù)為e，則其時(shí)間復(fù)雜度為O(eloge)。

總結(jié)

普里姆算法和克魯斯卡爾算法都有其適用范圍，雖然克魯斯卡爾算法的時(shí)間復(fù)雜度較低，但是它的實(shí)際值和邊的個(gè)數(shù)有很大關(guān)系，當(dāng)邊數(shù)很少時(shí)，它的效率十分高。而在邊數(shù)很多的稠密圖中，使用普里姆算法會更好一些。

我是飛機(jī)醬，如果您喜歡我的文章，可以關(guān)注我~

編程之路，道阻且長。唯，路漫漫其修遠(yuǎn)兮，吾將上下而求索。