克魯斯卡爾算法(Kruskal)

克魯斯卡爾（Kruskal）算法從另一途徑求網(wǎng)的最小生成樹。其基本思想是：假設連通網(wǎng)G=（V，E），令最小生成樹的初始狀態(tài)為只有n個頂點而無邊的非連通圖T=（V，{}），圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點分別在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊而選擇下一條代價最小的邊。依此類推，直至T中所有頂點構(gòu)成一個連通分量為止 [2] 。

和普利姆算法以頂點去構(gòu)建最小生成樹不同的是，克魯斯卡爾算法以邊來構(gòu)建最小生成樹?？唆斔箍査惴ǖ臅r間復雜度為O(eloge)。它針對與稀疏圖的效率較高。注意：初始化條件一定包含的是對邊集的排序算法。

最核心的其實就是這個簡單的Find算法，要理解并且記住它。

#include "鄰接矩陣"
typedef struct {
    int begin;
    int weight;
    int end;
} Edge;/*Kruskal算法所需要用到的邊集*/
void Kruskal(MGraph G){
    int i, n, m;
    Edge edges[MAXEDGE];
    int parent[MAXVEX];
    /*此處省略了將一個鄰接矩陣轉(zhuǎn)換為對應的邊集表的代碼，這部分代碼很簡單*/
    /*同時也省略了對于邊集edges的排序算法：edges[i]是從i = 0 到 i = G.numEdges 從小到大遞增的*/
    for(i = 0; i < G.numVexes; i++){
        n = Find(parent, edges[i].begin);
        /*分別找到 第i條邊的起始點頂和尾頂點的下一個結(jié)點(這個信息存放在parent數(shù)組)*/
        /*對于i=0的時候，parent數(shù)組全為0，所以返回的時候n是肯定不等于m的*/
        m = Find(parent, edges[i].end);
        /*這兩個值如果不相等意味著沒有形成環(huán)，反之則是形成了環(huán)*/
        if(n != m){
            parent[n] = m; 
            /*表明n到m之間是有路的。對parent的理解非常重要！
            這里有篇博客講的不錯：https://blog.csdn.net/qq_31709249/article/details/100855661?utm_medium=distribute.pc_relevant.none-              task-blog-BlogCommendFromBaidu-6.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-                                BlogCommendFromBaidu-6.channel_param
            */
            printf("(V%d V%d) %d", edges[i].begin, edges[i].end, edges[i].weight);
            /*打印邊信息*/
        }
    }
}
int Find(int * parent, int f){
    while(parent[f] > 0){
        f = parent[f];
    }
    return f;
}

對于Parent數(shù)組的理解(不對請指出啦??！)

n == m 的情況:

image

n != m 的情況:

image