一、最小生成樹的prim算法和Kruskal算法的區(qū)別

Kruskal算法（克魯斯卡算法）

Kruskal算法是一種貪心算法，我們將每個edge按照權重大小進行排序，每次從邊集中取出權重最小且兩個頂點都不在同一個集合的邊加入生成樹中！注意：如果這兩個頂點都在同一集合內，說明已經通過其他邊相連，因此如果將這個邊添加到生成樹中，那么就會形成環(huán)！這樣反復做，直到所有的節(jié)點都連接成功！

在這個算法中，最重要的一環(huán)就是判斷兩個節(jié)點在不在同一個集合內，很多人想，那你直接用一個set來保存不就好了？這是思路顯然不行，因為假設A和其他三個節(jié)點相連，同屬一個集合，而B和另外三個節(jié)點相連，同屬一個集合，那么我們將A和B取并集時，是將這兩組數據合并一起的，如果使用set，那么當數據量大時還需要遍歷，復雜度就會很高，因此使用并查集就會效率快很多了！

并查集詳解和STL中的自定義哈希

?mp.weixin.qq.com/s/gGCQ9uqlNQYbBHtw83xgOw

對所有節(jié)點遍歷建立并查集，按照邊的權重建立最小堆

取出最小堆堆頂數據，并判斷兩端節(jié)點是否在同一集合

如不在，則將這兩個節(jié)點添加到同一集合，接著將邊加入生成邊，如在，則不進行操作，為無效邊

重復上面的操作，直到所有的邊都檢查完

unordered_set kruskalMST(Graph graph){

??? auto cmp = [](const Edge& a, const Edge& b){

??????? return a.weight > b.weight;??? // 最小堆

??? };

??? vector list;

??? for(auto ite: graph.nodes){

??????? list.push_back(ite.second);

??? }

??? UnionFindSet unionFind(list);?? // 建立并查集

??? priority_queue, decltype(cmp)> smallQueue(cmp);

??? for(auto edge: graph.edges){

??????? smallQueue.push(*edge);

??? }

??? // 構造選中的輸出邊集

??? unordered_set result;

??? while(!smallQueue.empty()){

??????? Edge edge = smallQueue.較好();

??????? smallQueue.pop();

??????? if(!unionFind.isSameSet(edge.from, edge.to)){?

// 判斷是否為一個環(huán)，如果一個邊的兩端節(jié)點為一個集合，那么必為一個閉合環(huán)

??????????? result.insert(edge);

??????????? unionFind.Union(edge.from, edge.to);

??????? }

??? }

??? return result;

}

Prim算法（普里姆算法）

Prim算法是另一種貪心算法，和Kuskral算法的貪心策略不同，Kuskral算法主要對邊進行操作，而Prim算法則是對節(jié)點進行操作，每次遍歷添加一個點，這時候我們就不需要使用并查集了。具體步驟為：

建立邊set用來存放結果，建立節(jié)點set用來存放節(jié)點同時用于標記是否被訪問過，建立邊的最小堆

開始遍歷所有節(jié)點，如果沒有訪問，則添加到節(jié)點set，然后將其相連的邊入堆。

從堆中取最小的邊，然后判斷to節(jié)點是否被訪問過，如果沒有，將這個邊加入生成樹（我們想要的邊），并標記該節(jié)點訪問。

然后將to節(jié)點所相連的邊添加到最小堆中，不然這個網絡就不會向外擴展了（這個步驟是必須的）。

循環(huán)上面的操作，直到所有的節(jié)點遍歷完。

注意：對于單連通，從一個節(jié)點出發(fā)就可以直接找到完整的最小生成樹，因此最外的for循環(huán)也可以為一個順序結構，但多連通，就需要從不同的節(jié)點出發(fā)了！！！

unordered_set primMST(Graph graph){

??? // 裝邊的最小堆

??? auto cmp = [](const Edge& e1, const Edge& e2){

??????? return e1.weight > e2.weight;

??? };

??? priority_queue, decltype(cmp)> smallQueue(cmp);

??? // 判斷節(jié)點是否訪問過

??? unordered_set node_set;

??? unordered_set result;

??? for(auto ite: graph.nodes){

??????? if(node_set.find(*ite.second) == node_set.end()){

??????????? // 如果沒有訪問,將其標記為訪問過，并把它對應的邊放入最小堆

??????????? node_set.insert(*ite.second);

??????????? for(Edge* edge: ite.second->edges){

??????????????? smallQueue.push(*edge);

??????????? }

??????????? // 在當前這個圖中尋找最小生成樹

??????? ????while(!smallQueue.empty()){

??????????????? // 從堆中取出一個最小權重邊，并取出對應節(jié)點

??????????????? Edge help_edge = smallQueue.較好();

??????????????? smallQueue.pop();

??????????????? Node edge_to = *(help_edge.to);

??????????????? // 然后判斷這個節(jié)點是否被訪問過，如果沒有則將這個邊加入邊集

? ??????????????if(node_set.find(edge_to) == node_set.end()){

??????????????????? result.insert(help_edge);

??????????????????? node_set.insert(edge_to);?? // 標記edge_to也已經訪問過了

??????????????????? for(Edge *newEdge: edge_to.edges){

??????????????????????? smallQueue.push(*newEdge);

??????????????????? }

??????????????? }

??????????? }

??????? }

??? }

??? return result;

}

那么對于這兩種算法，我們應該用哪種呢？記得某個人說過這句話，算法沒有優(yōu)劣，每個算法都有它的使用場景，在對的場合使用對的算法，這才是算法工程師應該做的事情！

由于Kruksal算法是對邊進行操作，先取出邊，然后判斷邊的兩個節(jié)點，這樣的話，如果一個圖結構非常的稠密，那么Kruksal算法就比較慢了，而Prim算法只是對節(jié)點進行遍歷，并使用set進行標記，因此會相對于Kruksal算法，在稠密圖方面好很多，因此Kruksal算法常用于稀疏圖，而Prim算法常用于稠密圖！

延伸閱讀：

二、什么是最小生成樹

在給定一張無向圖，如果在它的子圖中，任意兩個頂點都是互相連通，并且是一個樹結構，那么這棵樹叫做生成樹。當連接頂點之間的圖有權重時，權重之和最小的樹結構為最小生成樹！

在實際中，這種算法的應用非常廣泛，比如我們需要在n個城市鋪設電纜，則需要n-1條通信線路，那么我們如何鋪設可以使得電纜最短呢？最小生成樹就是為了解決這個問題而誕生的！

上一篇

堆和樹有什么區(qū)別?

下一篇

樹堆（Treap）和紅黑樹（RB-Tree）各有哪些優(yōu)劣?