Kruskal算法怎么使用

這篇文章主要講解了“Kruskal算法怎么使用”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Kruskal算法怎么使用”吧！

先拋出個問題，什么是并查集，它有什么用？

其實并查集顧名思義就是有“合并集合”和“查找集合”兩種操作的關于數據結構的一種算法

1 什么是并查集，以及并查集要完成的目標。

舉個例子，通火車要修路，已經修了一部分了，但各個地方零零散散的沒有統一成一個整體的鐵路網，中國這么多地方，我不能每個地方都直接聯系，這樣花費的代價也太大了。所以我們這樣想，只要從一個地方能去中國任意一個地方就好了，用不著每個地方都相互有專門的鐵路。這就衍生了一個問題，我怎么知道我要去的地方在不在我這個鐵路網里？我該不該修到這兒的鐵路？不好判斷是吧，這就用到了并查集思想。

并查集主要用在判斷一個圖中的兩個頂點是否能相聯通的問題。

2 實現并查集的思想。

既然頂點與頂點能直接相同，那么他們一定處于同一張連通網中。因此，我們可以把不同的連通網分別看成一個個集合。我們要判斷兩點是否相通，可以檢索這兩點是否在同一張連通網里，在就能相通，反之不能。

所以，我們應該怎樣設計，使得我們能判斷兩點是否在同一張網里是問題的關鍵。

這時，我們自然而然的想到了，如果每一個點都能用這個網中的固定點表示（姑且把這個點稱為BOSS），那么問題就解決了。例如下圖，我們要判斷A和B是否能相通，A找啊找

找到A的BOSS是BOSS1，B也找啊找，找到B的BOSS也是BOSS1。說明他們位于同一張聯通圖中，即他們能過去。

   但是這找BOSS還是好麻煩，不好找，如果是兩棵樹的話就好多了，直接以根節點作為所有節點的BOSS，每棵樹只需要知道它自己的上級是誰，一層一層往上找，最終就找到BOSS了。例如：要找G和B是否位于同一張網，G開始找BOSS，G的上級是D，D的上級是A，A就是BOSS，返回G的BOSS為A。同理，B找到BOSS也是A。說明他們位于同一張網中。再例如我要判斷E和N是否能相通，我就找E的BOSS，再找N的BOSS，明顯A不等于H。所以他們不能連通。

總而言之，并查集就是把每堆元素合并為一個具有相同BOSS的集合，如果兩堆元素BOSS不同，說明他們不連通，反之連通。

3 實例代碼實現

我認為主體分為四個部分

（1）建立并查集（用數組也好，鏈表也行），我就用數組舉個例子

            int parent[maxSize];

           i表示頂點編號 parent[i]表示i對應的上級 ！！！

           這里下標代表頂點編號，元素代表它的上級（就是通過上級找上級.....最終能找到它的BOSS）。

（2）初始化并查集

for(int i  = 0 ; i < N;++i)   
{  
   parent[i] = i;  
}

 這里的N代表頂點的個數，首先默認每個頂點都不能互相聯系，每一個頂點自己就是一個集合，故a[i] = i;它的上級就是它自己，它就是BOSS。

（3）構造一個查找BOSS的算法，我用迭代的方式給出（遞歸也能寫）

int getBoss(int a)  
{  
    while(a != parent[a])    
    {  
        a = parent[a];  
    }  
    return a ;  
}

while循環的意思的如果傳進來的a已經是BOSS，直接輸出，否則進行查找（[注]根據存放的值可以找到它上級，它的上級又繼續查找它上級的上級，直到a==parent[a]說明找到了，

（4）判斷將頂點合并進同一個集合（有同一個BOSS），我用迭代的方法做個例子

void merge()  
{  
    int a , b;  
    a = getBoss(c);  
    b = getBoss(d);  
    if(a != b)  
    {  
    parent[a] = b;  
    }  
}

      c，d代表傳進來的頂點元素下標，如果兩個BOSS不相等，說明不在同一棵樹中，即不會產生循環，把b歸于a的集合，從此他們就在一棵樹中，共同擁有一個BOSS

最后舉出一些實際應用的例子

整幅圖的連通性問題。比如隨意給你兩個點，讓你判斷它們是否連通，或者問你整幅圖一共有幾個連通分支，也就是被分成了幾個互相獨立的塊。問還需要修幾條路，實質就是求有幾個連通分支。等等。。

typedef struct//建立邊的集合  
{  
    int begin;//一個邊的開始  
    int end;//一個邊的結束  
    int weight;//這個邊的權值  
}Edge;  
  
int Find(int* parent, int f)//查找跟節點的函數  
{  
    while(parent[f] != f)//如果f傳過來的上級不是parent[f]  
    //要根據f找它上級。它的上級繼續找它的上級；知道parent[f] == f 就輸出  
    {  
        f = parent[f];  
    }  
    return f;  
}  
  
void Kruskal(MGraph G)  
{  
    Edge edges[numE];//定義邊集數組 用來存放所有邊  
    int parent[numV];//定義一個數組來判斷是否與邊形成環  
    //此行 將鄰接矩陣 轉化為邊集數組edges 并按照由小到大排序  
    for(int i=0;i<G.numV; i++)//頂點  
    {  
        parent[i] = i；//初始化每個頂點的上級是自身  
    }  
    for(int i=0;i<G.numE；i++)//循環每一條邊  
    {  
        int n = Find(parent, edge[i].begin);  
        int m = Find(parent, edge[i].end);  
        if(n!= m)//說明m和n 在不同的聯通集里面   
        {  
            parent[n] = m;//將m跟n 的兩個聯通集 通過(n.m)連接起來  
            cout<<"("<<edges[i].begin<<","<<edges[i].end  
            <<") "<<edges[i].weight;  
        }  
    }  
}

     路徑壓縮算法：建立門派的過程是用join函數兩個人兩個人地連接起來的，誰當誰的手下完全隨機。最后的樹狀結構會變成什么胎唇樣，我也完全無法預計，一字長蛇陣也有可能。這樣查找的效率就會比較低下。最理想的情況就是所有人的直接上級都是掌門，一共就兩級結構，只要找一次就找到掌門了。哪怕不能完全做到，也最好盡量接近。這樣就產生了路徑壓縮算法。

感謝各位的閱讀，以上就是“Kruskal算法怎么使用”的內容了，經過本文的學習后，相信大家對Kruskal算法怎么使用這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！