最优生成树算法的编程

《最优生成树算法的编程》由会员分享，可在线阅读，更多相关《最优生成树算法的编程（4页珍藏版）》请在金锄头文库上搜索。

1、最优生成树算法的编程最优生成树算法的编程图论中讲到的最优生成树在现实中有着广泛的应用，例如为给一些村庄供水而需要建造的管线系统等等。相对简单的图中要找出其最优生成树并不算难，但较为复杂的图中找出最优生成树就不太容易了，此时我们可以把相应的算法编写为求最优树的程序，用计算机快速的运算速度为我们尽快的找出最有生成树，本篇文章就主要讨论一下由 Kruskal 算法编写的相关程序。最优生成树的 Kruskal 算法为：（摘自图论及其应用，东南大学出版社）1.在连通赋权图 G 中选取边 e1，使 e1 的权尽可能小。2.若已选定边 e1,e2,.,ei，则从 E(G)e1,e2,.,ei中选取边 ei+

2、1,使满足以下两条：(1)Ge1,e2,.,ei不含回路；(2)在满足(1)的前提下，使 w(ei+1)尽可能小；3,当 2 不能执行时，停止。根据此算法，可编写相应的程序：用二维数组 ann来指代图中的顶点和边，例如 a12=5 指代顶点v1 和 v2 的连线（即图的边）的权为 5。int *cm; /数组 c 中变量指向排序后的数组 a 的变量void newturn(int *a,int n); /将 a 由小到大排序，并将地址赋给指针数组 cint openroad(int *b,int n); /判断是否会形成回路的函数void besttree(int *a,int n) /找出最

3、优树int bnn; /a 中某一变量不为 0 时令 b 中相应位置变量为 1 来标记，以此来最后得到需选取的边。newturn(a,n);int i,j,k=0;while (*ck!=0)for (i=0;in;i+)for (j=0;jn;j+)if (ck=if (openroad(b,n)=0)bij=0;k+;void newturn(int *a,int n)int i,j,k=0;for (i=0;in;i+)for (j=0;jn;j+)while (aij!=0)ck=for (i=0;in;i+)for (j=0;jn;j+)if (aij*ck) *ck=aij;k+;aij=0;int openroad(int *b,int n,int bij)for (int m=0;mn;m+)for (int k=0;kn;k+)if (bik=0|bmj=0) return 1;if (bjk!=0) openroad(b,n,bjk);if (bmi!=0) openroad(b,n,bmi);return 0;由此在遇到较为复杂的求图的最优生成树时即用此程序快速的求出最优生成树。雷晓东 0620011908.12.20