您當(dāng)前位置：首頁 > php開源 > php教程 > 016-kruskal算法-貪心-《算法設(shè)計技巧與分析》M.H.A學(xué)習(xí)筆記

016-kruskal算法-貪心-《算法設(shè)計技巧與分析》M.H.A學(xué)習(xí)筆記

來源：程序員人生發(fā)布時間：2016-07-07 19:24:57 閱讀次數(shù)：3033次

最小生成樹：

在1給定的連通無向圖G = (V, E)中，(u, v) 代表連接頂點u與頂點v的邊，而 w(u, v)代表此邊的權(quán)重，若存在T為G的子集且為無循環(huán)圖，使得w(T) 最小，則此T為G的最小生成樹。

基本思路：

kruskal算法總共選擇n- 1條邊，所使用的貪婪準(zhǔn)則是：從剩下的邊當(dāng)選擇1條不會產(chǎn)生環(huán)路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產(chǎn)生環(huán)路則不可能構(gòu)成1棵生成樹。kruskal算法分e 步，其中e 是網(wǎng)絡(luò)中邊的數(shù)目。按耗費遞增的順序來斟酌這e 條邊，每次斟酌1條邊。當(dāng)斟酌某條邊時，若將其加入到已選邊的集合中會出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。

概括以下：

1. 對G的邊按權(quán)重非降序排列。

2. 1次取權(quán)重最小的邊，如果把它放入T不會構(gòu)成回路的話，則把它放入T中，否則將它拋棄。

判斷是不是構(gòu)成回路用并查集。

偽代碼：

算法分析：

主要耗費在邊的排序，時間復(fù)雜度為O(mlogm)。

C++代碼：

struct edge { int u, v, c; bool operator < (const edge &b) const { return c < b.c; } }e[mxe]; int n, m; int fa[mnx]; int find(int x) { if(fa[x] != x) fa[x] = find(fa[x]); return fa[x]; } // kruskal 復(fù)雜度O(|E|log|E|), |E|:邊數(shù) int kruskal() { sort(e + 1, e + m + 1); // 邊排序 for(int i = 1; i <= n; ++i) fa[i] = i; //并查集初始化 int ret = 0; for(int i = 1; i <= m; ++i) { int u = e[i].u, v = e[i].v, c = e[i].c; u = find(u), v = find(v); if(u != v) { //不在同1個集合里面,則把這1條邊加入成為最小生成樹的1部份 ret += c; fa[u] = v; } } return ret; }

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
程序員人生