1. 克魯斯卡爾算法簡介

克魯斯卡爾（Kruskal）算法是一種用來尋找最小生成樹的算法（用來求加權(quán)連通圖的最小生成樹的算法）。在剩下的所有未選取的邊中，找最小邊，如果和已選取的邊構(gòu)成回路，則放棄，選取次小邊。

而具體的操作過程為：

a) 將圖的所有連接線去掉，只剩頂點(diǎn)

b) 從圖的邊集數(shù)組中找到權(quán)值最小的邊，將邊的兩個(gè)頂點(diǎn)連接起來

c)  繼續(xù)尋找權(quán)值最小的邊，將兩個(gè)頂點(diǎn)之間連接起來，如果選擇的邊使得最小生成樹出現(xiàn)了環(huán)路，則放棄該邊，選擇權(quán)值次小的邊

d) 直到所有的頂點(diǎn)都被連接在一起并且沒有環(huán)路，最小生成樹就生成了。

2. 兩個(gè)核心問題

問題一 對圖的所有邊按照權(quán)值大小進(jìn)行排序。

問題二 將邊添加到最小生成樹中時(shí)，怎么樣判斷是否形成了回路。

問題一直接采用排序算法進(jìn)行排序即可。

問題二的核心思想是記錄處理，處理方式是：記錄頂點(diǎn)在"最小生成樹"中的終點(diǎn)，頂點(diǎn)的終點(diǎn)是"在最小生成樹中與它連通的最大頂點(diǎn)"。然后每次需要將一條邊添加到最小生存樹時(shí)，判斷該邊的兩個(gè)頂點(diǎn)的終點(diǎn)是否重合，重合的話則會(huì)構(gòu)成回路。

3. 代碼實(shí)現(xiàn)

依舊是僅供參考

#include<stdio.h>
 
#define MAXEDGE 100
#define MAXVERTEX 100
typedef struct Edge {
    int begin;//邊的起點(diǎn)
    int end;  //邊的終點(diǎn)
    int wight;//邊的權(quán)值
} Edge;
 
typedef struct Graph {
    char vertex[MAXVERTEX];//頂點(diǎn)
    Edge edges[MAXEDGE];//邊
    int numvertex,numedges;//頂點(diǎn)和邊的個(gè)數(shù)
} MGraph;
 
void CreateGraph(MGraph* G) {
    printf("請輸入頂點(diǎn)和邊的個(gè)數(shù)：\n");
    scanf("%d%d", &G->numvertex, &G->numedges);
    printf("請輸入頂點(diǎn)：\n");
    getchar();//利用該函數(shù)除去上一系我們在輸入結(jié)束時(shí)按得回車符
    for (int i = 0; i < G->numvertex; i++) {
        scanf("%c", &G->vertex[i]);
    }
    printf("按權(quán)值從小到大輸入邊（vi,vj）對應(yīng)的起點(diǎn)和終點(diǎn)的下標(biāo)，begin，end以及權(quán)值wight:\n");
    for (int k = 0; k < G->numedges; k++) {
        Edge e;
        scanf("%d%d%d", &e.begin, &e.end, &e.wight);
        G->edges[k] = e;
    }
}
 
int Find(int *parent, int f) {
    while (parent[f]>0) {
        f = parent[f];
    }
    return f;
}
 
//最小生成樹，克魯斯卡爾算法
void Kruskal(MGraph *G) {
 
    int parent[MAXVERTEX];//存放最小生成樹的頂點(diǎn)
    for (int i = 0; i < G->numvertex; i++) {
        parent[i] = 0;
    }
    int m, n;
    for (int i = 0; i < G->numedges; i++) {
        n = Find(parent, G->edges[i].begin);
        m = Find(parent, G->edges[i].end);
        if (n != m) { //m=n說明有環(huán)
            parent[n] = m;
            printf("(%d,%d) %d\t", G->edges[i].begin, G->edges[i].end, G->edges[i].wight);//打印邊和權(quán)值
        }
    }
}
 
int main() {
    MGraph G;
    CreateGraph(&G);
    Kruskal(&G);
 
    return 0;
}