最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
* E  r3 z0 u" v6 N0 A% Gn= size(a,1);
a_copy=a;
for i= 1:n
    for j=i:n
        a_copy(i,j)=inf;
    end
" B4 M; }  i. \end
+ X) {+ e. `1 ^( @( k( [: x& xtree_martix=zeros(n,n);
count=0;

tree_node=zeros(2*n,1);
i=1;
/ G* Z6 W& o( D5 z+ {# O4 G5 Mwhile count<=n-2
    b=min(min(a_copy));
0 ^$ w; U+ E+ R4 ^; l% b1 n0 u3 I    [index_x,index_y]=find(a_copy==b);
9 u! [, j0 g2 e! @' Z/ j& `! \+ u+ F% d% N     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
     a_copy(index_x,index_y)=inf;
  }1 P$ x5 ]6 h/ L, F1 v1 h     a_copy(index_y,index_x)=inf;
        continue;
3 i# K; O3 N* f. p! c' i  }    end
    tree_node(i)=min(index_x);
+ ]! e. N1 |3 ]    tree_node(i+1)=min(index_y);
1 S4 [# K- y1 M3 J/ R6 O. o    i=i+2;
    %a_copy(index_x,index_y)=inf;
    %a_copy(index_y,index_x)=inf;
6 \9 c* E+ W! ^2 V6 d    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
    a_copy(index_x,index_y)=inf;
- y0 {% ~7 a2 \+ D/ K( z8 D    a_copy(index_y,index_x)=inf;
   
( w( ?/ y- u/ B8 T    count=count+1;
   
end
tree_border=tree_node;
-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
* E2 c& c9 H5 s5 R  d2 Yflag=0;
# q: \) n' r. m# \* K& N) W8 G' `n=length(tree_node);
flag_x=0;
flag_y=0;
for i= 1:n
    if tree_node(i)==index_x
        flag_x=1;
( t* i! _* Q' L* t( R2 E    end
  b. i% P  C* v1 s$ E3 Y: x    if tree_node(i)==index_y
) h$ v* o! @0 p, \% r7 |        flag_y=1;
    end
- y, p# l* [- Z$ K1 z5 xend
if flag_x==1&&flag_y==1
, g9 L2 B; l7 [+ P( i. D# o. l    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
. x$ i  m, ~- k& `4 p8 @

qluther

弱弱的问问楼主，a是什么矩阵

qluther

程序好像有问题吧：只是把权矩阵中的最小值一次加入到tree_border中，没有管是否已经联通所有的点，或者是否构成圈了，希望LZ解答

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

qluther 发表于 2010-8-15 12:41
程序好像有问题吧：只是把权矩阵中的最小值一次加入到tree_border中，没有管是否已经联通所有的点，或者是否 ...

# j1 ?9 _; f6 M$ I找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...