您當前位置：首頁 > php開源 > php教程 > 016-kruskal算法-貪心-《算法設計技巧與分析》M.H.A學習筆記

016-kruskal算法-貪心-《算法設計技巧與分析》M.H.A學習筆記

來源：程序員人生發布時間：2016-07-07 19:24:57 閱讀次數：3027次

最小生成樹：

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

基本思路：

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

概括以下：

1. 對G的邊按權重非降序排列。

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

判斷是不是構成回路用并查集。

偽代碼：

算法分析：

主要耗費在邊的排序，時間復雜度為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 復雜度O(|E|log|E|), |E|:邊數 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; }

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生