Kruscal算法求圖的最小生成樹

概述

? 和Prim算法求圖的最小生成樹一樣，Kruscal算法求最小生成樹也用到了貪心的思想，只不過前者是貪心地選擇點，后者是貪心地選擇邊。而且在算法的實現中，我們還用用到了并查集（也稱不相交集的）Union /Find 算法來判斷兩個節點連通后會不會形成一個環。該算法的思想很簡單：將圖的所有邊按從小到大順序排序，每次都選取權值最小的邊加入最小生成樹，如果該邊的加入會使生成樹形成一個環，則跳過該邊。
? 這里引入并查集的概念，可以使問題變得簡單化。并查集就是利用一個數組sets，如果sets[a]=b，那么我們說a和b在一個生成樹（集合）中，且a的雙親是b，如果sets[a]=a,那么我們說a是一個生成樹的根。一個圖的最小生成樹在還沒有完全生成前，可能存在多個互不連通的生成樹，他們是不相交的集合，我們需要把這些不同的生成樹連通起來。
?于是，通過定義一個findroot函數，我們可以找到某頂點的雙親，然后找到該頂點的雙親的雙親，最終找到頂點所在最小生成樹的根，例如：如果我們知道sets[a]=b,sets[b]=c,sets[c]=c，那我們可以說a、b、c在同一棵生成樹(集合)里，且所在最小生成樹的根為c。假設另一個不相交的生成樹的根為d，如果我們令sets[c]=d,則將這兩個生成樹合并為了一個大的生成樹，其根為d。

算法圖解

1.創建一個9條邊，6個頂點的帶權無向連通圖。

初始狀態的并查集如下：

2.將圖所有邊按權值進行排序。選擇權值最小的一條邊的兩個鄰點。為了避免混亂，統一約定該邊右邊的鄰點加入左邊的鄰點的并查集中，在圖中表示為2頂點掛在1頂點下面。


3.就這樣，按照權值從小到大不斷遍歷所有邊，都統一把邊的大序號的鄰點加入小序號的鄰點所在的生成樹中，3頂點掛在2頂點下面，4頂點掛在3頂點下面，5頂點掛在4頂點下面，6頂點掛在2頂點的下面，最終最小生成樹不斷長大，且最后所有頂點本質上都掛在1頂點下面，即最小生成樹的根為1頂點。


4.最好還剩4條邊沒有遍歷。但我們發現，這4條邊的兩個鄰點都在同一個生成樹中了，即他們findroot的結果都是1。如果我們把任意一條邊的兩個鄰點連接起來，都會形成一個環，這是不允許的。故最小生成樹的生成就此結束。

代碼

1.引入頭文件，和之前所講的的其他圖論算法不同的是，這里單獨定義一個表示圖的邊的類，用u，v記錄邊的鄰接點，w記錄邊的權值。

#include<iostream>
#include<vector>
#include<algorithm>
 //這里同之前我們實現prim算法用的鄰接矩陣不同
 //我們用一直特殊的儲存方式儲存圖的邊
 using namespace std;

struct edge{
    //邊的兩個鄰點，其中u編號小于v編號
    int u;
    int v;
    //邊的權值
    int w;
};

2.定義表示圖的類

struct Graph{
    //儲存邊的容器
    vector<edge> edges;
    //定義并查集,記錄各頂點的“根”，確定各頂點是否在同一棵樹里
    vector<int> sets;
    //構造函數
    Graph(int vertexnum,int edgenum);
    //析構函數
    ~Graph();
    //kruascal算法的調用接口
    void kruscal();
    //尋根函數，后面會詳細講解其用途
    int findroot(int vertex);
    //按權值給圖的邊排序的函數
    void sortedges();
};

3.這里自定義一個排序比較函數，后面給儲存邊的容器排序時會用到。

//排序自定義操作函數
bool cmp(edge a,edge b){
    return a.w<=b.w;
}

4.Graph類的構造函數以及析構函數

Graph::Graph(int vertexnum,int edgenum){
    edges.resize(edgenum+1);
    sets.resize(vertexnum+1);
    //初始化并查集。每個節點相互獨立，自己是自己所在生成樹的根
    for(int i=1;i<=vertexnum;i++){
        sets[i]=i;
    }
    cout<<"請依次輸入各邊的兩個頂點及其權值"<<endl;
    //注意，為了跟后面尋根函數配合，要保證u定點編號小于v頂點編號
    for(int i=1;i<=edgenum;i++){
        int a,b,w;
        cin>>a>>b>>w;
        if(a>b){
            edges[i].u=a;
            edges[i].v=b;
        }
        else{
            edges[i].v=a;
            edges[i].u=b;
        }
        edges[i].w=w;
    }
}
Graph:: ~Graph(){
    edges.clear();
    sets.clear();
}

5.Kruscal算法的實現。

 //kruascal算法的實現方法
void Graph::kruscal(){
    //調用成員函數對圖的所有邊進行排序
    sortedges();
    int sum=0;
    for(int i=1;i<=edges.size()-1;i++){
        /*如果該邊的兩個頂點的根不相同，則讓u鄰接點成為v鄰接點的根的根。
        說形象一點，就是讓v鄰接點的BOSS歸順于u鄰接點的BOSS；
        從而讓v歸順于u的BOSS，
        并將該邊的權值加入總和中 */
        if(findroot(edges[i].u)!=findroot(edges[i].v)){
            sets[findroot(edges[i].v)]=findroot(edges[i].u);
            //此處非常容易錯，讀者寫代碼時一定要仔細
            sum += edges[i].w;
        }
        //否則不進行任何操作
    }
    cout<<"最小生成樹的權值和為："<<sum<<endl;
}

6.尋根函數的實現

//利用并查集性質，逐步回溯，找到一個頂點的“根”
 int Graph::findroot(int vertex){
    while(sets[vertex]!=vertex){
        vertex=sets[vertex];
    }
    return vertex;
}

7.對頂點按照權值排序函數的實現

//按權值對頂點進行從小到大排序的函數
void Graph::sortedges(){
    sort(edges.begin(),edges.end(),cmp);
}

8.測試部分。定義一個6個頂點9條邊的圖，調用接口求該圖的最小生成樹

int main()
{
    //實例化一個6個頂點，9條邊的圖對象
    Graph* G=new Graph(6,9);
    //調用接口實現算法
    G->kruscal();
    system("pause");
    return 0;
}

輸出

控制臺輸出結果：