最小数prim算法

水木年华zzu

求最小树的prim算法
* _# c2 u: }# L' l% q说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
* }4 ]" o5 j. tn= size(a,1);
9 r* Y4 F. e7 S: t, ea_copy=a;
7 ]$ y0 `+ C( p2 r9 a8 p! B% Y5 }for i= 1:n
    for j=i:n
( V  L1 p6 V0 d5 l2 k        a_copy(i,j)=inf;
2 z; g% E* ^$ y* \, B; q    end
end
tree_martix=zeros(n,n);
- V" ]& E, i/ C$ bcount=0;

tree_node=zeros(2*n,1);
i=1;
" ?  ^* w7 t* _1 B) m$ |6 e$ Z5 qwhile count<=n-2
    b=min(min(a_copy));
    [index_x,index_y]=find(a_copy==b);
" C4 u% [3 E8 z5 Y     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
) Z* z7 k/ R* l) Z7 W) f     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
        continue;
    end
5 e6 }# z; n- p    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
  V7 k$ d0 P& q. M    i=i+2;
    %a_copy(index_x,index_y)=inf;
    %a_copy(index_y,index_x)=inf;
. _- v# f+ r( l! ?1 [+ H4 ^  b: K    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
, h5 p6 z0 \; g; O$ s( E    a_copy(index_x,index_y)=inf;
4 ]- d) {5 b( g& s& D: H+ o& f    a_copy(index_y,index_x)=inf;
   
    count=count+1;
   
end
8 r; ?2 f1 `5 F7 @1 I8 I7 Ltree_border=tree_node;
: T9 k' L1 {1 B-----------------------------
" w$ M6 a# r) n- |% }1 W. Efunction flag=node_judge(tree_node,index_x,index_y)
flag=0;
" c/ G% K- M  w1 @4 z9 p6 s. H; V4 p9 Nn=length(tree_node);
( @& ?9 F$ O9 y6 Q4 j+ M2 X6 iflag_x=0;
7 s$ F; m! r5 q/ sflag_y=0;
/ `" I2 A/ X6 C% Gfor i= 1:n
1 y" }! W- P# F6 `2 P    if tree_node(i)==index_x
/ _% `+ z2 I2 X3 s* ]) v3 X        flag_x=1;
    end
    if tree_node(i)==index_y
        flag_y=1;
    end
end
if flag_x==1&&flag_y==1
    flag=1;
9 |& V. R3 j( H' S% rend

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...