以文本方式查看主题

-  趣题之家  (http://www.qthome.org/bbs/index.asp)
--  算法艺术  (http://www.qthome.org/bbs/list.asp?boardid=38)
----  最小生成树  (http://www.qthome.org/bbs/dispbbs.asp?boardid=38&id=292)
--  作者：remlostime
--  发布时间：3/15/2005 11:09:44 PM

--  最小生成树
最小生成树


假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。


    在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢？


　　普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法是两个利用MST性质构造最小生成树的算法。








1







2







3







4







5







6







①







②







③







④







⑤







⑥⑤







6







5







5







6

program prim;


  const max=6;


of byte=((0,6,1,5,0,0),


                                        (6,0,5,0,3,0),


                                        (1,5,0,5,6,4),


                                        (5,0,5,0,0,2),


                                        (0,3,6,0,0,6),


                                        (0,0,4,2,6,0));


of byte=(100,100,100,100,100); 扩展用数组，ss=0表示I点已扩展，ss<>0表示ss是当前所有已扩展点到点I的路径中的最短路径。


<>0表示I点与j点连


of byte; 存ss的另一端点，即s[I,p]=ss


       i,j,l,m,n:integer;


  begin


:=0; 清零


<>0 then begin ss:=s[1,i];p:=1 end;


                                          ss数组赋初值，并找出与1点相通的所有点。


    for i:=2 to max do


      begin


        l:=100;


        for j:=2 to max do  找出与当前树中所有点相连的最短边中的最小边


end


建树


则替换


) then


:=n end;


      end;


    for i:=1 to max do  输出最小生成树矩阵


);writeln end;


    writeln


  end.
--  作者：licong
--  发布时间：3/21/2005 1:37:36 PM

--  
普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法是两个利用MST性质构造最小生成树的算法。

MST?


网上贸易 创造奇迹! 阿里巴巴 Alibaba

Powered By Dvbbs Version 7.1.0
Copyright ©2003 - 2006 QTHome.Org
页面执行时间 00.21875 秒, 2 次数据查询
 本论坛采用阿里巴巴支付宝网上银行支付系统，安全、可靠、便捷