數據結構之克魯斯卡爾算法

前言：和Prim算法一樣，Kruskal 算法也是用來生成最小生成樹的，這篇文章來學習一下Kruskal算法的實現

一、實現流程

初始化的時候，將所有的邊用一個數組存儲，并且按權值從小到大進行排序，每次選一個權值最小的邊加入到生成樹中，但是在加入之前，需要判斷加入的這條邊會不會使生成樹形成環路。接下來我們分步驟看一下算法的執行過程
我們來看這樣一個圖
在這里插入圖片描述
1、邊數組初始化
從小到大存儲邊

2、權值最小，為1的邊連接4號節點和6號節點，這兩個節點不在同一棵樹中，不會形成環路，因此加入生成樹
在這里插入圖片描述
3、下一個權值最小的邊，0-2 ，權值為2，這個邊及加入生成樹也不會形成環路，所以加入生成樹

4、下一個權值最小的邊是 5-7，同上也直接加入樹

5、下一個邊 0-2，同樣加入生成樹

6、下一個 0-3 的邊，也不會形成環路，加入
在這里插入圖片描述

7、下一個 3-5 的邊也可以加入生成樹
在這里插入圖片描述

8、下一個 0-4 ，也可以直接加入
在這里插入圖片描述

9、至此，所有的節點已經全部加入到生成樹中，算法結束

二、代碼實現

1、定義常數

#define MaxSize 100
#define MaxEdge 200  // 最大邊數
#define MaxVex 100   // 最大頂點數

2、結構體

需要兩個結構體，一個是圖，一個是邊
圖需要包括點的個數，邊的個數，和鄰接矩陣

typedef struct {int vexnum;  // 頂點數int arcnum;  // 邊數int arcs[MaxVex][MaxVex];  // 鄰接矩陣
} MGraph;

邊的結構體需要包含邊的兩個頂點，和邊的權值

typedef struct{int a,b; // 邊的兩個頂點int weight; // 邊的權值
} Edge

3、初始化變量和工具函數

需要一個邊數組，存儲所有的邊

Edge edges[MaxEdge]; // 變數組

Kcuscal 算法需要找權值最小的邊，所以對所有的邊進行排序，c語言中有一個內置的 qsort 方法，可以對任何類型進行排序，接收四個參數：
參數一：void* base，待排數組
參數二：size_t num，待排元素的個數
參數三：size_t size，每個元素的大小，單位為字節，使用 sizeof() 函數獲取
參數四：int (*compare)(const void * , const void *)，排序函數
需要一個排序函數 compare，將權值比較小的邊放在前面
void * 表示泛型指針類型，表示a可以指向任何類型的數據
(Edge*) 是一個類型轉換，由于在入參中我們定義的 a 可以是任何類型的數據，這里使用 (Edge*) 將a轉換為指向 Edge 結構體的指針。
Edge *edgeA 聲明了一個新指針，并且將 a 指針的值賦值給它，現在 edgeA 就是一個指向 Edge 結構體的指針。
返回值，如果是負數，表示 edgeA->weight 小，則不更換數據的位置；如果是正數，表示 edgeA->weight 小，則要更換數據的位置。

int compare(const void *a, const void *b){Edge *edgeA = (Edge *) a;Edge *edgeB = (Edge *) b;return edgeA->weight - edgeB->weight;
}

另外判斷邊是否能夠加入到生成樹中的時候，需要判斷這條邊和生成樹是不是在同一棵樹中，如果在同一棵樹中，那么加入這條邊，一定會形成環路。我們在合并兩個樹的時候學過，將一個樹 A 合并到另一棵樹 B 中，就是將樹的根節點 A 的父節點更新成另一棵樹的根節點 B。
所以我們需要維護一個數組 parent，來存儲所有的節點的父節點，初始化的時候，都初始化為-1

int parent[MaxVex]; // 根節點數組（并查集）

節點當加入到生成樹中就需要進行合并操作，需要更新節點對應的根節點。
所以我們需要一個查找根節點的函數 Find，來查找一個節點所在的樹的根節點
如果 parent[x] 小于 0 ，說明當前節點還沒有加入到生成樹中，就直接返回節點本身。如果parent[x] 大于 0，則向上找父節點，直到找到 parent[x] 小于 0 的的點。

// 并查集的Find操作
int Find(int *parent,int x){while(parent[x]>=0) x=parent[x]; // 循環向上尋找下標為x頂點的根return x; // while循環結束時找到了根的下標
}

4、主函數

在主函數中需要做的事情：
1、給邊數組 edges 按權值排序
2、初始化 parent 數組為 -1
3、遍歷邊，找邊的兩個頂點的 parent，如果 parent 不相同，表示兩個頂點不在同棵樹中，則將其中一個頂點的 parent 指向另一個頂點，也就是將兩個頂點合并在一棵樹中

void MiniSpanTree_Kruskal(Gragh G){int i,n,m;// edges 排序qsort(edges, G.arcnum, sizeof(Edge), compare);// 初始化parentfor(i=0;i<G.vexnum;i++) parent[i] = -1;// 遍歷所有邊for(i=0;i<G.arcnum;i++){n = Find(edges[i].a);  // 第一個節點所在的樹的根節點m = Find(edges[i].b);  // 第二個節點所在的樹的根節點if(n!=m){  // 根節點不同，說明這兩個節點位于兩棵不同的樹，則合并這兩棵樹parent[n] = m;printf("(%d->%d) 權值:%d\n", edges[i].a, edges[i].b, edges[i].weight);}}
}

三、和Prim算法的對比

組成樹的元素有兩個，一個是節點，一個是邊。Prim 算法主要關注節點，找和當前的最小生成樹距離最近的節點，把節點加入到生成樹中。而Kruskal算法主要關注的是邊，先將所有的邊排序，將權值最小并且不會形成環路的邊依次加入到生成樹中。由于Kruskal算法要對邊進行對比排序，所以Kruskal算法的執行效率取決于邊的多少，適合邊少的圖，我們叫做稀疏圖。而Prim算法主要關注節點，適合邊多的圖（邊多就相當于節點少了），我們叫做稠密圖。
下面我們來分析一下時間復雜度，假設圖的節點數為 v ，邊數為 e，
Prim 算法需要執行兩層循環，每層執行的次數都是 v，所以Prim算法的時間復雜度是 O(v^2)。
Kruckal 算法 qsort()方法的時間復雜度是 O(elog2e)，它是時間復雜度最高的方法，
外層需要遍歷所有的邊，時間復雜度是 O(e)， Find 方法的并查集操作的時間復雜度可以優化到很小，可以忽略，所以整個算法的時間復雜度是 O(elog2e)

四、測試代碼

在 main 函數中，需要初始化 edges 數組

// 克魯斯卡爾算法
// 求最小生成樹的算法
#include <stdio.h>
#include <stdlib.h>#define MaxSize 100
#define MaxEdge 200  // 最大邊數
#define MaxVex 100   // 最大頂點數// 圖的鄰接矩陣表示
typedef struct {int vexnum;  // 頂點數int arcnum;  // 邊數int arcs[MaxVex][MaxVex];  // 鄰接矩陣
} MGraph;typedef struct {int a,b; // 邊的兩個頂點int weight; // 邊的權值
}Edge;// 并查集的Find操作
int Find(int *parent,int x){while(parent[x]>=0) x=parent[x]; // 循環向上尋找下標為x頂點的根return x; // while循環結束時找到了根的下標
}// 比較函數，用于qsort排序
// const 放在*的左邊，表示指針指向的數據不可變，但是指針的指向可變
int compare(const void *a, const void *b) {Edge *edgeA = (Edge*)a;Edge *edgeB = (Edge*)b;return edgeA->weight - edgeB->weight; // 按權值從小到大排序
}Edge edges[MaxEdge]; // 邊數組
int parent[MaxVex]; // 父親頂點數組（并查集）void MiniSpanTree_Kruskal(MGraph G){int i,n,m;// printf("\n排序前的邊數組：\n");// for(i=0; i<G.arcnum; i++) {//     printf("(%d-%d) 權值:%d\n", edges[i].a, edges[i].b, edges[i].weight);// }// 按權值由小到大對邊排列qsort(edges, G.arcnum, sizeof(Edge), compare);// printf("\n按權值排序后的邊數組：\n");// for(i=0; i<G.arcnum; i++) {//     printf("(%d-%d) 權值:%d\n", edges[i].a, edges[i].b, edges[i].weight);// }for(i=0;i<G.vexnum;i++) parent[i]=-1; // 初始化并查集// printf("\n最小生成樹的邊：\n");for(i=0;i<G.arcnum;i++){ // 遍歷每一條邊n=Find(parent,edges[i].a); // n是這條邊的第一個頂點的根節點所在的下標m=Find(parent,edges[i].b); // m是這條邊的第二個頂點的根節點所在的下標if(n!=m){parent[n] = m; // 并操作printf("(%d->%d) 權值:%d\n", edges[i].a, edges[i].b, edges[i].weight);}}
}// 初始化圖的邊
void initGraph(MGraph *G) {// 示例圖：6個頂點，9條邊G->vexnum = 6;  // 頂點數 0-5G->arcnum = 9;  // 邊數// 手動添加邊的信息到edges數組// 頂點0-1，權值4edges[0].a = 0; edges[0].b = 1; edges[0].weight = 4;// 頂點0-2，權值6edges[1].a = 0; edges[1].b = 2; edges[1].weight = 6;// 頂點0-3，權值16edges[2].a = 0; edges[2].b = 3; edges[2].weight = 16;// 頂點1-2，權值10edges[3].a = 1; edges[3].b = 2; edges[3].weight = 10;// 頂點1-4，權值7edges[4].a = 1; edges[4].b = 4; edges[4].weight = 7;// 頂點2-3，權值14edges[5].a = 2; edges[5].b = 3; edges[5].weight = 14;// 頂點2-4，權值3edges[6].a = 2; edges[6].b = 4; edges[6].weight = 3;// 頂點2-5，權值8edges[7].a = 2; edges[7].b = 5; edges[7].weight = 8;// 頂點4-5，權值9edges[8].a = 4; edges[8].b = 5; edges[8].weight = 9;
}int main() {MGraph G;// printf("=== 克魯斯卡爾最小生成樹算法演示 ===\n\n");// 初始化圖initGraph(&G);// printf("原始圖的邊信息：\n");// printf("頂點數：%d，邊數：%d\n", G.vexnum, G.arcnum);// printf("所有邊：\n");// for(int i = 0; i < G.arcnum; i++) {//     printf("(%d-%d) 權值:%d\n", edges[i].a, edges[i].b, edges[i].weight);// }// printf("\n開始執行克魯斯卡爾算法：\n");// printf("================================\n");// 執行克魯斯卡爾算法MiniSpanTree_Kruskal(G);// printf("================================\n");// printf("算法執行完成！\n");return 0;
}