摘要

生成樹是一種圖的表現形式，它有個簡單的規定，就是邊的數量等于頂點的數量減一。在有權圖中找到最小生成樹在很多場景中被應用到。這裡主要介紹一種獲取最小生成樹的方法，即 Prim。還有另外一種，下期繼續。

生成樹也被稱為支撐樹，在連通圖中，它的極小連通子圖就是生成樹。極小連通子圖包含連通圖中全部的 n 個頂點，連接的邊恰好隻有 n-1 條（這裡讨論無向圖）。如下圖所示的連通圖：

它的極小連通子圖可以有如下3種（其實可以還有其他種）：

看極小連通子圖，可以總結出圖中的頂點與邊的關系為，邊 = 頂點 - 1。

最小生成樹

最小生成樹通常也可以被稱為最小權重生成樹或者最小支撐樹，即所有的生成樹中，總的權值最小的那棵樹。既然提到權重，那麼最小生成樹就是适用于有權的連通圖（依然讨論的是無向的）。如下圖所示，右側部分就是最小生成樹：

打個最小生成樹應用的場景。假如要在多個城市之間鋪設光纜，讓它們之間可以通信。鋪設光纜的費用比較高，而且每個城市之間的距離不同等等因素，造成不同城市之間鋪設光纜的費用不同，如何以最低的費用鋪設光纜呢？最小生成樹就是解決的方案。

有一點要留意，在一個圖中，每一條邊的權值都互不相同，那麼最小生成樹隻會有一個，否則可能會存在多個最小生成樹。

現在求最小生成樹有2個經典算法，分别是 Prim（普裡姆算法）和 Kruskal（克魯斯克爾算法）

Prim 算法

學習 Prim 算法之前，需要了解切分定理，它是 Prim 定理的核心操作。

切分就是把圖中的節點切分為兩部分，這被稱作一個切分，如下圖所示：

這裡将圖切分成兩部分，頂點 A、B、C 是一部分，D、E 是一部分。紅色邊被稱為橫切邊，即一個邊的兩個頂點，分别屬于切分的兩部分，那麼這個邊就被稱為橫切邊，如圖 BD、BE、CE 就是橫切邊。

切分定理就是給定任意的切分，橫切邊中權值最小的邊必定屬于最小生成樹。

Prim 算法執行時，假設一個有權的連通圖（無向的）為 G（包含頂點和邊），A 為 G 中的最小生成樹。再定義一個存放頂點的集合 S，起始 S 中的頂點遠小于 G 中的頂點。然後進行切分操作（後面提到），直到 S 和 G 中的頂點的數量相同。

切分操作是先找到切分 C = (S, V-S) 的最小橫切邊，并入到 A 中，同時将其頂點并入到集合 S 中，重複這樣的操作。如下圖所示（從左到右，從上到下，注意圖中的幾個元素，綠色的頂點、藍色的頂點、黑色的邊、綠色的邊、紅色的邊、虛分割線、權值）：

圖中以頂點 B 開始進行切分，紅色邊就是橫切邊，綠色頂點部分是最小生成樹集合。這裡有幾個核心操作：

1. 綠色頂點與藍色頂點相連的邊就是橫切邊，也是每次切分的部分；
2. 橫切邊中選擇權值最小的，劃分到綠色部分（最小生成樹），然後将該邊設置為綠色，權值相等，就随便選擇一條邊；
3. 當全部頂點都是綠色時，查看圖中還是黑色的邊，删除它，一個最小生成樹就完成了。

先上代碼，通過代碼再來梳理一遍：

Set<EdgeInfo<V, E>> prim() { iterator<Vertex<V, E>> it = vertices.values().iterator(); if (!it.hasNext()) return null; Vertex<V, E> vertex = it.next(); Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>(); Set<Vertex<V, E>> addedVertices = new HashSet<>(); addedVertices.add(vertex); MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges, edgeComparator); int verticesSize = vertices.size(); while (!heap.isEmpty() && addedVertices.size() < verticesSize) { Edge<V, E> edge = heap.remove(); if (addedVertices.contains(edge.to)) continue; edgeInfos.add(edge.info()); addedVertices.add(edge.to); heap.addAll(edge.to.outEdges); } return edgeInfos; }

prim 函數返回的是 EdgeInfo 類型的集合，Edgeinfo 主要存放的是起始頂點、結束頂點和權值：

public static class EdgeInfo<V, E> { private V from; private V to; private E weight; public EdgeInfo(V from, V to, E weight) { this.from = from; this.to = to; this.weight = weight; }

prim 函數中的前三行代碼是保證圖集合是否存在頂點，并獲取第一個頂點，這裡使用了叠代器的方式來處理（其他方式也可以）：

Iterator<Vertex<V, E>> it = vertices.values().iterator(); if (!it.hasNext()) return null; Vertex<V, E> vertex = it.next();

接下來創建存放 Edgeinfo 和存放最小生成樹頂點的集合 addedVertices，存放第一個頂點，準備後面的切分操作。

這裡使用 MinHeap 存放放入 addedVertices 中頂點的出度邊，MinHeap 是小頂堆，會将其中的邊按照權值，将最小的權值放在一個位置，後面再添加的邊也會及時更新，一隻保持權值最小的邊在第一位（對小頂堆感興趣可以看《數據結構與算法-基礎（十九）堆》文章）。

MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges, edgeComparator);

最後就是不停将 heap 中權值最小的邊拿出來，放入到 Edgeinfo 集合中，将邊的結束頂點放入 addedVertices 中，再将結束頂點的邊繼續放入 heap 中。如果這個邊的結束頂點已經在 addedVertices 中，就不做前面的操作。直到 addedVertices 中的頂點數量和圖中的頂點數量相同結束。

也有一種情況，就是 heap 中的元素沒有了，這時也是完成了，最後部分代碼，看上面最開始的部分。

總結

• 生成樹也被稱為支撐樹，圖中的邊數量等于頂點數量減一就可以被稱為生成樹，一個圖中的生成樹有很多；
• 最小生成樹是權值最小總和最小的生成樹，在權值互不相同的圖中，最小生成樹隻有一個；
• Prim 是求最小生成樹的算法，它使用切分的方式處理，其中用到小頂堆的數據結構。

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部