kruskal算法求最小生成樹

1、kruskal算法求最小生成樹課題：用kruskal算法求最小生成樹。編譯工具：Visual Studio 2017kruskal算法基本思想：先構(gòu)造一個只含 n個頂點、而邊集為空的子圖，把子圖中各個頂點看成各棵樹上的根結(jié)點，之后，從網(wǎng)的邊集E中選取一條權(quán)值最小的邊，若該條邊的兩個頂點分屬不同的樹，也即則將其加入子圖，即把兩棵樹合成一棵樹，反之，若該條邊的兩個頂點已落在同一棵樹上， 則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直到森林中只有一棵樹，子圖中含有n-1條邊為止。問題：按如下連通圖用kruskal算法求最小生成樹。程序源碼：#include #include using n

2、amespace std;const int N = 100;int nodesetN;int n, m;struct Edge /int u;int v;int w;eN*N;bool comp(Edge x, Edge y) /return x.w y.w;void Init(int n) /for (int i = 1; i = n; i+)nodeseti = i;int Merge(int a, int b)/int p = nodeseta;/p定義結(jié)構(gòu)體配合 sort() 方法對權(quán)值進(jìn)行升序?qū)咸?nodeset 數(shù)組進(jìn)行初始化將 ei.u 結(jié)點傳遞給 a; ei.v 結(jié)點傳遞

3、給 b.為 a 結(jié)點的集結(jié)號，int q = nodesetb;/q為 b 結(jié)點的集結(jié)號if (p = q) return 0;/判斷結(jié)點間是否回環(huán)。若兩個結(jié)點的集結(jié)號相同，則不操作，直接返回。for (int i = 1; i = n; i+)/ 是 q 的改為 p.if (nodeseti = q)nodeseti = p;return 1;int Kruskal(int n)int ans = 0;若兩個結(jié)點的集結(jié)號不相同，檢查所有結(jié)點，把集合號for (int i = 1; i=m; i+)if (Merge(ei.u, ei.v)cout A 結(jié)點：vv ei.u B 結(jié)點： ei.

4、v endl; / 各結(jié)點ans += ei.w;n-;if (n = 1)return ans;return 0;輸出滿足條件的int main() cout 輸入總結(jié)點數(shù)(n)和總邊數(shù)(m) : n m;In it (n);cout 輸入結(jié)點數(shù)(u),(v) 和權(quán)值(w) : endl;for (i nt i = 1; i ei.u ei.v ei.w;sort(e+1, e + m+1, comp);int ans = Kruskal( n);cout 最小的花費(fèi)是： ans endl;return 0;源碼流程解析：(1)在ma in ()中，輸入結(jié)點數(shù) n與邊m n=7， m=12在

5、In it (n) 中，對nodeseti 進(jìn)行初始化。下標(biāo)i1234567集合號1234567(3)使用sort ()方法按權(quán)值進(jìn)行升序排序。eiuvwe1372e2124e3354e4564e5576e6677e7168e8238e9349e104510e112611e122714調(diào)用 kruskal(n)方法，(n=7,m=12)。for (i nt i = 1; i=m; i+)if (Merge(ei.u, ei.v)/調(diào)用 int Merge(int a, int b)方法cout A 結(jié)點： ei.u B 結(jié)點： ei.v endl;ans += ei.w;n-;if (n =

6、1)retur n ans;return 0;int Merge(int a, int b)/int p = nodeseta;/pint q = nodesetb;/qif (p = q) return 0;/則不操作，直接返回。for (int i = 1; i = n; i+)/ 是 q 的改為 p.if (nodeseti = q)nodeseti = p;將 ei.u 結(jié)點傳遞給 a; ei.v 結(jié)點傳遞給 b.為 a 結(jié)點的集結(jié)號，為 b 結(jié)點的集結(jié)號 .判斷結(jié)點間是否回環(huán)。若兩個結(jié)點的集結(jié)號相同，若兩個結(jié)點的集結(jié)號不相同，檢查所有結(jié)點，把集合號return 1;(5)示意圖分析abno desetano desetbPq373737121212353535563636573333673333161313231111341414no desetiansn12345632611345632+4511343632+4+4411343332+4+4+43回環(huán)，直接返回回環(huán)，直接返回11141 1 12+4+4+4+82回環(huán)，直接返回11111112+4+4+4+8+9=311e4/10(6)輸出結(jié)果當(dāng)n=1時，退出循環(huán)，程序結(jié)束8e3424e7