kruskal算法求最小生成树

1、kruskal算法求最小生成树课题：用kruskal算法求最小生成树。编译工具：Visual Studio 2017kruskal算法基本思想：先构造一个只含 n个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，也即则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上， 则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，子图中含有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定义结构体配合 sort() 方法对权值进行升序对集合号 nodeset 数组进行初始化将 ei.u 结点传递给 a; ei.v 结点传递

3、给 b.为 a 结点的集结号，int q = nodesetb;/q为 b 结点的集结号if (p = q) return 0;/判断结点间是否回环。若两个结点的集结号相同，则不操作，直接返回。for (int i = 1; i = n; i+)/ 是 q 的改为 p.if (nodeseti = q)nodeseti = p;return 1;int Kruskal(int n)int ans = 0;若两个结点的集结号不相同，检查所有结点，把集合号for (int i = 1; i=m; i+)if (Merge(ei.u, ei.v)cout A 结点：vv ei.u B 结点： ei.

4、v endl; / 各结点ans += ei.w;n-;if (n = 1)return ans;return 0;输出满足条件的int main() cout 输入总结点数(n)和总边数(m) : n m;In it (n);cout 输入结点数(u),(v) 和权值(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 最小的花费是： ans endl;return 0;源码流程解析：(1)在ma in ()中，输入结点数 n与边m n=7， m=12在

5、In it (n) 中，对nodeseti 进行初始化。下标i1234567集合号1234567(3)使用sort ()方法按权值进行升序排序。eiuvwe1372e2124e3354e4564e5576e6677e7168e8238e9349e104510e112611e122714调用 kruskal(n)方法，(n=7,m=12)。for (i nt i = 1; i=m; i+)if (Merge(ei.u, ei.v)/调用 int Merge(int a, int b)方法cout A 结点： ei.u B 结点： 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 结点传递给 a; ei.v 结点传递给 b.为 a 结点的集结号，为 b 结点的集结号 .判断结点间是否回环。若两个结点的集结号相同，若两个结点的集结号不相同，检查所有结点，把集合号return 1;(5)示意图分析abno desetano desetbPq373737121212353535563636573333673333161313231111341414no desetiansn12345632611345632+4511343632+4+4411343332+4+4+43回环，直接返回回环，直接返回11141 1 12+4+4+4+82回环，直接返回11111112+4+4+4+8+9=311e4/10(6)输出结果当n=1时，退出循环，程序结束8e3424e7