最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
7 M( G( ]& v/ D; o" |1 ]function [tree_martix,tree_border]=min_tree(a)
$ Y# k9 P5 ^: q4 bn= size(a,1);
a_copy=a;
- x6 q- j( f' P) v1 d0 lfor i= 1:n
    for j=i:n
- i  E, n: P. k        a_copy(i,j)=inf;
    end
end
tree_martix=zeros(n,n);
7 o( \. E! u) ]$ @. z- Fcount=0;
) _7 y1 W9 b. E% N+ s2 v! K
tree_node=zeros(2*n,1);
i=1;
while count<=n-2
    b=min(min(a_copy));
' c( ~. M# h! N& H& i* z" t7 f# x    [index_x,index_y]=find(a_copy==b);
2 L; {! F  E" _0 q5 g+ ]     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
     a_copy(index_x,index_y)=inf;
, O# ^6 H2 d7 P' h9 H6 F     a_copy(index_y,index_x)=inf;
        continue;
    end
    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;
    a_copy(index_y,index_x)=inf;
! B8 H: \7 R# `# m1 i, l   
2 C, F6 }+ S: k3 G8 M7 K, l    count=count+1;
   
$ q* c7 J, w! L% r# G& \/ Kend
tree_border=tree_node;
-----------------------------
" R0 C8 K* Z% L9 g4 xfunction flag=node_judge(tree_node,index_x,index_y)
flag=0;
& s' @1 Q: v. O, p" J4 ]9 Dn=length(tree_node);
flag_x=0;
flag_y=0;
1 q# g2 X$ T# mfor i= 1:n
5 ?: F. Z* s( s+ g    if tree_node(i)==index_x
        flag_x=1;
( v: I' Y( Y6 ?3 g0 b5 u6 u    end
    if tree_node(i)==index_y
        flag_y=1;
    end
7 v* m1 r. y9 `' {# |+ Lend
7 I& f4 @+ c$ T/ p# }if flag_x==1&&flag_y==1
: t/ {1 c8 w8 ]) R    flag=1;
end

朱鑫鑫

...

小叮当1016

谢谢分享程序～

水木年华zzu

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

找几个矩阵验算下就行了

效忠w手掌

谢谢分享程序的人，

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

qluther

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

qluther

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

zhangkay

谢谢分享程序～
+ k' |: W# O7 T% u. G) T

大笨象

谢谢分享程序～