最优生成树算法的编程.doc_第1页
最优生成树算法的编程.doc_第2页
最优生成树算法的编程.doc_第3页
最优生成树算法的编程.doc_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论