在研究Prim算法之前，首先要了解一個概念。切分定理

切分定理

切分（Cut）：把圖中的節(jié)點(diǎn)分為兩部分，成為一個切分

例如下圖，該圖上有5個頂點(diǎn)

現(xiàn)在，利用虛線，將圖分割為2部分，第一部分有3個節(jié)點(diǎn)，第二部分有2個節(jié)點(diǎn)，這就叫做一個切分

所以切分可以通過這種式子來進(jìn)行表示C = (S,T)，其中S = {A，B，D}，T = {C，E}

橫切邊（Crossing Edge）：如果一個邊的兩個頂點(diǎn)，分別屬于切分的兩部分，這個邊就稱為橫切邊

所以上圖中的邊BC,BE,DE就是橫切邊，因?yàn)檫@些邊，一部分在左邊的子圖中，一部分在右邊的子圖中。

切分定理：給定任意切分，橫切邊中權(quán)值最小的邊必然屬于最小生成樹

意思就是說，如上圖的3條橫切邊，權(quán)值最小的一條，必然屬于最小生成樹的邊

Prim算法執(zhí)行過程

假設(shè)G = （V,E）是有權(quán)的連通圖（無向），A是G中最小生成樹的邊集

1. G表示圖，V表示頂點(diǎn)，E表示邊
2. 組成最小生成樹的邊都會放到集合A中
3. A最開始的時候，是一個空集合

再定義一個集合S，用來存放切分的起點(diǎn)和切完后被切出來的頂點(diǎn)，所以集合S中的頂點(diǎn)都是屬于V的，然后重復(fù)找到切分的最小橫切邊，然后將找到的邊存放到結(jié)合A中，同時將找到的頂點(diǎn)放入集合S中。直到S = V為止，就說明找到了最小生成樹的所有邊和頂點(diǎn)。

以上執(zhí)行過程比較抽象，如果將上面流程轉(zhuǎn)換為流程圖，則可以通過下面的流程來進(jìn)行表示

假設(shè)現(xiàn)在有如下的圖，現(xiàn)在從頂點(diǎn)A開始進(jìn)行切分，所以首先將A加入到集合S中

在對頂點(diǎn)A進(jìn)行切分，所以以頂點(diǎn)A的outEdges進(jìn)行切分，利用虛線表示如下

通過這樣切分以后，就會產(chǎn)生2條橫切邊，分別為4和8，結(jié)合前面的切分定理，最終會選擇AB這條邊最為最小生成樹的邊，現(xiàn)在找出了一條最小生成樹的邊，所以將AB這條邊加入到集合A中，并且將橫切邊的另外一頂點(diǎn)B加入到集合S中，現(xiàn)在集合S中就存放了2個頂點(diǎn){A，B}，最終切分后的結(jié)果如下

現(xiàn)在相當(dāng)于將圖切為了兩個部分，一部分的頂點(diǎn)存放在集合S中，另外一部分繼續(xù)存放在原來的內(nèi)存中。所以以集合S中的頂點(diǎn)與原來圖中的頂點(diǎn)，將兩個部分中有邊存在的部分作為一個切邊，所以最終的切分如下

切邊找到后，又根據(jù)切分定理，找出去權(quán)值最小的一條邊，然后將邊放入到集合A中，將橫切邊的另外一頂點(diǎn)放入集合S中，由于現(xiàn)在有兩條邊權(quán)值相同，所以任意選擇一條均可。在本示例中選擇BC條邊，所以現(xiàn)在將新找到的一條邊加BC入到A中，并且將C加入到S中，現(xiàn)在S中就存放了3個頂點(diǎn){A,B,C}，切分后的結(jié)果如下

再利用前面尋找切分的方法，可以找到如下圖所示的切分

根據(jù)現(xiàn)在的切分，找出 權(quán)值最小的邊CI，將邊CI加入到集合A中，另外一頂點(diǎn)I加入到S中，所以最終切分后的結(jié)果如下

再利用前面尋找切分的方法，可以找到下一個如下圖所示的切分

這樣一切，又可以找到權(quán)值最小的橫切邊CF，所以將邊CF加入到結(jié)合A中，將頂點(diǎn)F加入到集合S中，最終切分后的結(jié)果如下

繼續(xù)尋找新的切分，所以，很容易就知道新的切分如下所示

然后又從橫切邊中找出權(quán)值最小的邊，所以本次權(quán)值最小的邊為GF，所以將GF這條邊加入到集合A中，頂點(diǎn)G加入到S中，最終切分后的結(jié)果如下

繼續(xù)進(jìn)行切分，找出一條最小生成樹的邊，所以本次的切分如下。不過需要注意，這里有一個小細(xì)節(jié)，IG這條邊沒有被最為一條橫切邊，原因是如果將這條邊作為橫切邊以后，萬一被選中，那么原來的最小生成樹就會成環(huán)，這就不符合最小生成樹的要求，所以在選擇很切邊時，可能有一些小細(xì)節(jié)需要注意

根據(jù)上面的切分，最終又會選擇出一條權(quán)值最小的邊HG，將這表邊加入到集合A中，同時將H加入到集合S中，所以最終切分后的結(jié)果如下

繼續(xù)進(jìn)行切分，本次的切分如下所示

找出權(quán)值最小的邊CD，將邊CD加入到集合A中，將新的頂點(diǎn)D加入到S中，所以本次切分后的結(jié)果如下

繼續(xù)進(jìn)行切分，本次氣氛如下圖所示

找出權(quán)值最小的邊DE，將DE加入到結(jié)合A中，將新的頂點(diǎn)E加入到集合S中，所以本次切分的結(jié)果如下

到現(xiàn)在可以發(fā)現(xiàn)，原來圖中的所以頂點(diǎn)，都已經(jīng)加入到了集合S中，所以即表示最小生成樹已經(jīng)完成。所以去掉多于的線以后，最終的最小生成樹如下

所以經(jīng)過這樣一個流程下來，相信已經(jīng)可以理解前面最新過程部分的概括了。

結(jié)合前面的分析，得到代碼如下

private Set<EdgeInfo<V, E>> prim() {
    Iterator<Vertex<V,E>> it = vertices.values().iterator();
    if (!it.hasNext()) return null;
    Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
    Set<Vertex<V,E>> addedVertices = new HashSet<>();
    Vertex<V,E> vertex = it.next();
    addedVertices.add(vertex);
    MinHeap<Edge<V,E>> heap = new MinHeap<>(vertex.outEdges,edgeComparator);
    int edgeSize = vertices.size() - 1;
    while (!heap.isEmpty() && edgeInfos.size() < edgeSize) {
        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;
}

demo下載地址

完！