今天數(shù)據(jù)結(jié)構(gòu)課講了最小生成樹(shù)的Kruskal算法和Prim算法，不過(guò)都只是概念，可能是怕他們聽(tīng)不懂吧，反正算法實(shí)現(xiàn)一概不講...囧

下午抱著《算法導(dǎo)論》跑去圖書(shū)館看Kruskal算法，發(fā)現(xiàn)《算法導(dǎo)論》真的是牛XXXX的書(shū)啊，看完之后豁然開(kāi)朗，而且驚訝地發(fā)現(xiàn)Kruskal算法居然用到了前兩天研究的并查集，爽歪歪了...

Kruskal比較適用于稀疏圖，是一種貪心算法:為使生成樹(shù)上邊的權(quán)值和最小，則應(yīng)使生成樹(shù)中每一條邊的權(quán)值盡可能地小。

具體做法:找出森林中連接任意兩棵樹(shù)的所有邊中，具有最小權(quán)值的邊，如果將它加入生成樹(shù)中不產(chǎn)生回路，則它就是生成樹(shù)中的一條邊。這里的關(guān)鍵就是如何判斷"將它加入生成樹(shù)中不產(chǎn)生回路"。

《算法導(dǎo)論》提供的一種方法是采用一種"不相交集合數(shù)據(jù)結(jié)構(gòu)"，也就是并查集了。具體的實(shí)現(xiàn)看代碼好了，反正核心內(nèi)容就是如果某兩個(gè)節(jié)點(diǎn)屬于同一棵樹(shù)(Find_Set)，那么將它們合并(Union)后一定會(huì)形成回路。

編寫(xiě)程序:對(duì)于如下一個(gè)帶權(quán)無(wú)向圖，給出所有邊以及權(quán)值，用kruskal算法求最小生成樹(shù)。

輸入數(shù)據(jù):

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
Total:39

代碼如下，其實(shí)代碼可以?xún)?yōu)化的地方很多，例如當(dāng)生成樹(shù)的邊數(shù)已經(jīng)等于n-1時(shí)即可停止循環(huán)...因?yàn)椴皇茿CM題，故優(yōu)化省略不寫(xiě)，只當(dāng)做算法學(xué)習(xí)...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107

#include <stdio.h> #include <stdlib.h>#define MAX 100/* 定義邊(x,y)，權(quán)為w */ typedef struct {int x, y;int w; }edge;edge e[MAX]; /* rank[x]表示x的秩 */ int rank[MAX]; /* father[x]表示x的父節(jié)點(diǎn) */ int father[MAX]; int sum;/* 比較函數(shù)，按權(quán)值(相同則按x坐標(biāo))非降序排序 */ int cmp(const void *a, const void *b) {if ((*(edge *)a).w == (*(edge *)b).w){return (*(edge *)a).x - (*(edge *)b).x;}return (*(edge *)a).w - (*(edge *)b).w; }/* 初始化集合 */ void Make_Set(int x) {father[x] = x;rank[x] = 0; }/* 查找x元素所在的集合,回溯時(shí)壓縮路徑 */ int Find_Set(int x) {if (x != father[x]){father[x] = Find_Set(father[x]);}return father[x]; }/* 合并x,y所在的集合 */ void Union(int x, int y, int w) {sum += w;if (x == y) return;/* 將秩較小的樹(shù)連接到秩較大的樹(shù)后 */if (rank[x] > rank[y]){father[y] = x;}else{if (rank[x] == rank[y]){rank[y]++;}father[x] = y;} }/* 主函數(shù) */ int main() {int i, n;int x, y;char chx, chy;/* 讀取邊的數(shù)目 */scanf("%d", &n);getchar();/* 讀取邊信息并初始化集合 */for (i = 0; i < n; i++){scanf("%c %c %d", &chx, &chy, &e[i].w);getchar();e[i].x = chx - 'A';e[i].y = chy - 'A';Make_Set(i);}/* 將邊排序 */qsort(e, n, sizeof(edge), cmp);sum = 0;for (i = 0; i < n; i++){x = Find_Set(e[i].x);y = Find_Set(e[i].y);if (x != y || (!x && !y)){printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w);Union(x, y, e[i].w);}}printf("Total:%d\n", sum);system("pause");return 0; }

總結(jié)

以上是生活随笔為你收集整理的最小生成树kruskal算法并查集版 C语言实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。