最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
! H4 K& M5 P8 y4 j3 Zfunction [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
a_copy=a;
for i= 1:n
    for j=i:n
        a_copy(i,j)=inf;
    end
end
3 c/ f! Z: I& C; G1 gtree_martix=zeros(n,n);
4 \4 ?1 |1 ?3 V! M: {2 b' p: mcount=0;

tree_node=zeros(2*n,1);
$ [" V4 t1 r+ S# Xi=1;
5 I% l3 V* o; \$ Twhile count<=n-2
    b=min(min(a_copy));
    [index_x,index_y]=find(a_copy==b);
     flag=node_judge(tree_node,index_x,index_y);
# W  e% @- d, Z: u/ ^    if flag==1
     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
" L  l. _, y! r( N8 `        continue;
- j: E0 c1 U% k% I    end
    tree_node(i)=min(index_x);
) E5 V" g; \' i& v    tree_node(i+1)=min(index_y);
    i=i+2;
- V6 O. a7 k& X$ p+ x. T5 s- \    %a_copy(index_x,index_y)=inf;
    %a_copy(index_y,index_x)=inf;
    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
    a_copy(index_x,index_y)=inf;
( r+ U: V! `2 H0 s, C8 |    a_copy(index_y,index_x)=inf;
   
    count=count+1;
4 m" J% t) c" E, H   
end
" T" C, z6 c1 Mtree_border=tree_node;
/ i- a1 T: Q. d( q6 B: Q9 D-----------------------------
' E. {8 q* d  }function flag=node_judge(tree_node,index_x,index_y)
, s$ q' x5 \' Eflag=0;
! Y3 ?' \; @, T& on=length(tree_node);
flag_x=0;
flag_y=0;
for i= 1:n
+ G7 j/ T. _" ]: [    if tree_node(i)==index_x
, U( [2 N. }' P; m: m% m: U  P2 Y        flag_x=1;
    end
" ]5 S1 U. ~- k0 |6 S    if tree_node(i)==index_y
/ w+ r5 z6 q/ [        flag_y=1;
    end
% _& O  Z2 Q- [/ q$ z- Z- P. g( lend
if flag_x==1&&flag_y==1
    flag=1;
end

朱鑫鑫

...

小叮当1016

谢谢分享程序～

水木年华zzu

qluther 发表于 2010-8-15 12:41
8 \* k) ^9 I9 W" {! u" w程序好像有问题吧：只是把权矩阵中的最小值一次加入到tree_border中，没有管是否已经联通所有的点，或者是否 ...

找几个矩阵验算下就行了

效忠w手掌

谢谢分享程序的人，

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

qluther

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

qluther

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

zhangkay

谢谢分享程序～

大笨象

谢谢分享程序～