最小数prim算法

水木年华zzu

求最小树的prim算法
, C2 R2 w0 I2 z5 x* L7 |1 H" _说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
3 \& f( ^) \0 l6 Rfunction [tree_martix,tree_border]=min_tree(a)
6 T9 ]- H( s( w) s8 ]& Pn= size(a,1);
a_copy=a;
0 A. ^) @4 J5 T, Rfor i= 1:n
    for j=i:n
1 R) _4 c, P7 u        a_copy(i,j)=inf;
    end
( Z6 T. }2 Z0 M; N& |8 qend
tree_martix=zeros(n,n);
6 L3 X4 F* s6 t# H) ?count=0;

tree_node=zeros(2*n,1);
i=1;
* P6 Z5 B  e" e- C. I2 M1 Bwhile count<=n-2
    b=min(min(a_copy));
4 H4 G  g8 o( b- B3 T    [index_x,index_y]=find(a_copy==b);
( z8 n7 q/ v: \  t* Z( m     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
     a_copy(index_x,index_y)=inf;
, e. R  T+ k9 q     a_copy(index_y,index_x)=inf;
: ~* @% i5 p" ~$ }; m5 P" M$ R        continue;
$ ^) y, O! C4 `, v! f! V5 K    end
# m; T& T+ o/ a) I    tree_node(i)=min(index_x);
# S/ V6 ?; I. H$ a. s' F9 ]    tree_node(i+1)=min(index_y);
9 L0 n$ Y: B0 D    i=i+2;
: S/ s! G! C3 n5 e) J% Q" h8 e3 ]    %a_copy(index_x,index_y)=inf;
    %a_copy(index_y,index_x)=inf;
5 V5 _  q  K/ Z, F    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
    a_copy(index_x,index_y)=inf;
    a_copy(index_y,index_x)=inf;
2 x' F' n7 ~9 [9 y- h   
4 b8 L' p) v5 l6 p% B$ @    count=count+1;
" a7 T' W/ p# ^, O0 ?  d/ s; v$ j   
- H" v6 v- W& L6 o$ D# p* fend
tree_border=tree_node;
+ r' s9 d: Y9 m' E: t8 T; x6 H* O8 m-----------------------------
' X6 K' w/ ^4 b' W6 S1 H+ Rfunction flag=node_judge(tree_node,index_x,index_y)
8 ~" \& S. M+ A& {4 E. w. qflag=0;
  ~1 ~9 p/ D& R' E5 F3 ^n=length(tree_node);
flag_x=0;
! |2 V! b0 f. b" fflag_y=0;
for i= 1:n
5 }7 U' j6 ~) L8 v4 A) }9 O/ ^    if tree_node(i)==index_x
        flag_x=1;
8 V$ w6 ^8 r  y8 L& a    end
    if tree_node(i)==index_y
' A. m. i  R/ W7 L        flag_y=1;
9 E8 w( d  t& h+ d6 l4 D0 W    end
end
. @+ a) N! g9 z: ~- r8 [if flag_x==1&&flag_y==1
    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...