文章和資源同步更新至微信公眾號：演算法工程師之路

8月份會在公眾號推出每日演算法題，值得期待哦~

上一篇文章，我們講了圖的創建和遍歷，其中遍歷的演算法主要有BFS（廣度優先演算法）和DFS（深度優先演算法）兩種，並且DFS演算法對很多問題都有很好的啟示！而今天我們要說一個非常實用的演算法——最小生成樹的建立！這是圖論中一個經典問題，可以使用Kruskal和Prim兩種演算法來進行實現！

什麼是最小生成樹

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

開啟圖結構的學習：圖的創建和遍歷?

mp.weixin.qq.com圖標

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

最小生成樹

如上圖所示，一幅兩兩相連的圖中，找到一個子圖，連接到所有的節點，並且連接邊的權重最小（也就是說邊的數量也是最小的，這也保證了其是樹結構）.

Kruskal演算法（克魯斯卡演算法）

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

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

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

mp.weixin.qq.com圖標
  1. 對所有節點遍歷建立並查集，按照邊的權重建立最小堆
  2. 取出最小堆堆頂數據，並判斷兩端節點是否在同一集合
  3. 如不在，則將這兩個節點添加到同一集合，接著將邊加入生成邊，如在，則不進行操作，為無效邊
  4. 重複上面的操作，直到所有的邊都檢查完

unordered_set<Edge, EdgeHash, EdgeEqual> kruskalMST(Graph graph){
auto cmp = [](const Edge& a, const Edge& b){
return a.weight > b.weight; // 最小堆
 };
vector<Node*> list;
for(auto ite: graph.nodes){
list.push_back(ite.second);
}
UnionFindSet unionFind(list); // 建立並查集
 priority_queue<Edge, vector<Edge>, decltype(cmp)> smallQueue(cmp);
for(auto edge: graph.edges){
smallQueue.push(*edge);
}
// 構造選中的輸出邊集
 unordered_set<Edge, EdgeHash, EdgeEqual> result;
while(!smallQueue.empty()){
Edge edge = smallQueue.top();

smallQueue.pop();
if(!unionFind.isSameSet(edge.from, edge.to)){
// 判斷是否為一個環，如果一個邊的兩端節點為一個集合，那麼必為一個閉合環
 result.insert(edge);
unionFind.Union(edge.from, edge.to);
}
}
return result;
}

Prim演算法（普里姆演算法）

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

  1. 建立邊set用來存放結果，建立節點set用來存放節點同時用於標記是否被訪問過，建立邊的最小堆
  2. 開始遍歷所有節點，如果沒有訪問，則添加到節點set，然後將其相連的邊入堆。
  3. 從堆中取最小的邊，然後判斷to節點是否被訪問過，如果沒有，將這個邊加入生成樹（我們想要的邊），並標記該節點訪問。
  4. 然後將to節點所相連的邊添加到最小堆中，不然這個網路就不會向外擴展了（這個步驟是必須的）。
  5. 循環上面的操作，直到所有的節點遍歷完。

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

unordered_set<Edge, EdgeHash, EdgeEqual> primMST(Graph graph){
// 裝邊的最小堆
auto cmp = [](const Edge& e1, const Edge& e2){
return e1.weight > e2.weight;
};
priority_queue<Edge, vector<Edge>, decltype(cmp)> smallQueue(cmp);
// 判斷節點是否訪問過
unordered_set<Node, NodeHash, NodeEqual> node_set;
unordered_set<Edge, EdgeHash, EdgeEqual> 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()){
// 從堆中取出一個最小權重邊，並取出對應節點
Edge help_edge = smallQueue.top();
smallQueue.pop();

Node edge_to = *(help_edge.to);
// 然後判斷這個節點是否被訪問過，如果沒有則將這個邊加入邊集
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;
}

那麼對於這兩種演算法，我們應該用哪種呢？記得某個人說過這句話，演算法沒有優劣，每個演算法都有它的使用場景，在對的場合使用對的演算法，這纔是演算法工程師應該做的事情！

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

資源分享

以上完整代碼文件（C++版）,文件名為：最小生成樹（Kruskal演算法和Prim演算法），請關注我的個人公眾號 （演算法工程師之路），回復"左神演算法基礎CPP"即可獲得，並實時更新！希望大家多多支持哦~

公眾號簡介：分享演算法工程師必備技能，談談那些有深度有意思的演算法，主要範圍：C++數據結構與演算法/深度學習（CV），立志成為Offer收割機！堅持分享演算法題目和解題思路（Day By Day)

演算法工程師之路

推薦閱讀：

相關文章