Kruskal算法怎么使用

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

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

其實并查集顧名思義就是有“合并集合”和“查找集合”兩種操作的關(guān)于數(shù)據(jù)結(jié)構(gòu)的一種算法

1 什么是并查集，以及并查集要完成的目標(biāo)。

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

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

2 實現(xiàn)并查集的思想。

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

所以，我們應(yīng)該怎樣設(shè)計，使得我們能判斷兩點是否在同一張網(wǎng)里是問題的關(guān)鍵。

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

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

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

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

3 實例代碼實現(xiàn)

我認(rèn)為主體分為四個部分

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

            int parent[maxSize];

           i表示頂點編號 parent[i]表示i對應(yīng)的上級 ?。?！

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

（2）初始化并查集

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

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

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

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

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

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

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

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

最后舉出一些實際應(yīng)用的例子

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

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

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

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