圖 之 MST（最小生成樹 — kruskal算法 ）并查集實作

#并查集的優化：

（1）       Find_Set(x)時，路徑壓縮尋找祖先時，我們一般采用遞歸查找，但是當元素很多亦或是整棵樹變為一條鍊時，每次Find_Set(x)都是O(n)的複雜度。為了避免這種情況，我們需對路徑進行壓縮，即當我們經過”遞推”找到祖先節點後，”回溯”的時候順便将它的子孫節點都直接指向祖先，這樣以後再次Find_Set(x)時複雜度就變成O(1)了，如下圖所示。可見，路徑壓縮友善了以後的查找。

（2）       Union(x,y)時，按秩合并，即合并的時候将元素少的集合合并到元素多的集合中，這樣合并之後樹的高度會相對較小。

【輸入】：

11

A B 7

A D 5

B C 8

B D 9

B E 7

C E 5

D E 15

D F 6

E F 8

E G 9

F G 11

【輸出】：

A - D : 5

C - E : 5

D - F : 6

A - B : 7

B - E : 7

E - G : 9

39

【代碼】：

#include<stdio.h>
#include<iostream>
#include<algorithm>

using namespace std;

#define max_num 100

/*
 * 表示圖的邊
 */
typedef struct edge {
    int x,y;
    int w;
} edge;

edge e[max_num];
int n = 0;

//定義并查集 的parent數組和rank數組（樹的深度-1——嚴謹的說）
int parent[max_num];
int rank[max_num];

//最小代價
int sum = 0;

//cmp函數-> 将e數組按權值w排序，當w相同，按x的升序
bool cmp(edge a,edge b) {
    if(a.w != b.w) {
        return a.w<b.w;
    } else {
        return a.x<b.x;
    }
}

/*
 * 并查集
 */
 void makeSet(int x) {
     parent[x] = x;
     rank[x] = 0;
 }

 int findSet(int x) {
     if(x != parent[x]) {
         parent[x] = findSet(parent[x]);
     }
     return parent[x];
 }

 void unionSet(int x, int y, int w) {
     sum += w;

     if(x == y) return;
    
     if(rank[x]>rank[y]) {
         parent[y] = x;
     } else {
         if(rank[x] == rank[y]) {
             rank[y]++;
         }
         parent[x] = y;
     }
 }

//圖的建立
 void creatGraph() {
     int x, y;
     char chx, chy;
     cin>>n;

     for(int i = 0; i<n; i++) {
         cin>>chx>>chy>>e[i].w;
       //  getchar();
         e[i].x = chx - 'A';
         e[i].y = chy - 'A';
         makeSet(i);
     }
 }
 
/*
 * kruskal algorithm
 * 1.按權值将邊數組排序
 * 2.按順序加入到MST中，前提是不會産生回路
 */
 void kruskal() {
     int x,y;

     sort(e,e+n,cmp);
 /*    
     for(int i = 0; i<n; i++) {
        cout<<e[i].w<<endl;
     }
     */
     for(int i = 0; i<n; i++) {
         x = findSet(e[i].x);
         y = findSet(e[i].y);

         if(x != y) {
             printf("%c - %c : %d\n",e[i].x+'A', e[i].y+'A', e[i].w);
             unionSet(x, y, e[i].w);
         }
     }
     cout<<sum<<endl;
 }

 int main() {

     creatGraph();
     kruskal();

     return 0;
 }