最小数prim算法

水木年华zzu

求最小树的prim算法
5 P7 K) J8 ?: M: e  _说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
; Y, x) q' S/ U5 Ifunction [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
a_copy=a;
for i= 1:n
    for j=i:n
- O0 c* J% Y$ Z% d        a_copy(i,j)=inf;
    end
/ u) a$ u2 L' ]end
2 F: H& r) ?+ Etree_martix=zeros(n,n);
count=0;

tree_node=zeros(2*n,1);
- n3 C; a# b- E1 i; V7 ~! X6 di=1;
while count<=n-2
9 }4 i. O  i# w  S/ f9 f& @3 l, O    b=min(min(a_copy));
* t9 u! M( H/ U0 s! X- K4 c  X    [index_x,index_y]=find(a_copy==b);
" B( @+ `, `# U" k3 M9 L& b     flag=node_judge(tree_node,index_x,index_y);
* y1 N- `8 H; U0 w    if flag==1
; o/ o. b) \$ Q% f- G/ d6 J* g     a_copy(index_x,index_y)=inf;
# ~+ X- s4 j& a) e/ Y! ~& ^     a_copy(index_y,index_x)=inf;
        continue;
  O2 K* D; N. V4 C    end
2 B2 v, Z& F+ K5 c- Q8 ~3 W    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
    i=i+2;
    %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;
7 Y" [, P! i- o9 j' o' L    a_copy(index_y,index_x)=inf;
   
6 `- x1 L/ O1 W7 H2 U, Q: K# b% z    count=count+1;
   
end
7 L9 u# M7 e: ~/ t+ n; G' xtree_border=tree_node;
-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
flag=0;
" B. l0 L' j/ z! n& Dn=length(tree_node);
flag_x=0;
& _) S( c$ C3 }6 N  j* @  |0 @flag_y=0;
for i= 1:n
    if tree_node(i)==index_x
5 d% q3 e- ^$ v8 T1 v/ X        flag_x=1;
* F0 s8 L- B  n: c5 x    end
    if tree_node(i)==index_y
& Z- [: Z% P0 W1 h" w        flag_y=1;
    end
end
) [7 Z8 C3 z+ \. Iif flag_x==1&&flag_y==1
1 \# p' U9 h$ M& }. W+ [    flag=1;
end

朱鑫鑫

...

小叮当1016

谢谢分享程序～

水木年华zzu

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

找几个矩阵验算下就行了

效忠w手掌

谢谢分享程序的人，

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

qluther

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

qluther

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

zhangkay

谢谢分享程序～

大笨象

谢谢分享程序～