最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
5 ~4 ]: O" m6 y1 m$ m, lfunction [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
) u& H5 Z6 l) X: za_copy=a;
for i= 1:n
: u. e" @" w+ E  v7 y. @- Q    for j=i:n
1 a9 P# a: l: B4 R        a_copy(i,j)=inf;
2 x& W0 Q6 o. i. [4 g    end
end
tree_martix=zeros(n,n);
4 D1 p! R; c; |% P( F5 [count=0;
! X$ J, Z  j8 V% x1 g$ @
+ S: k, b1 G% s  A. gtree_node=zeros(2*n,1);
2 y; Z; b& j. yi=1;
while count<=n-2
    b=min(min(a_copy));
    [index_x,index_y]=find(a_copy==b);
& O+ Z: i3 Q! Y+ S# F     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
     a_copy(index_x,index_y)=inf;
     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;
- W2 P8 J$ v: T+ L- }& c; F# L4 ^- x    %a_copy(index_x,index_y)=inf;
: j* }+ q8 `" V    %a_copy(index_y,index_x)=inf;
/ a4 v+ B1 |5 r& i1 n0 d7 H4 W    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
- R( r9 `2 K: v: m8 B% W    a_copy(index_x,index_y)=inf;
    a_copy(index_y,index_x)=inf;
/ M/ ?" E1 S/ Q+ Q& j   
4 G- ]- X" k6 S7 g7 ]! T( V) r    count=count+1;
' w5 ^) c: X, w$ [' r! h7 V) O+ w% s   
end
9 m2 r0 v6 g) W, Qtree_border=tree_node;
! x7 Q: `. Y$ b& `, C. r-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
flag=0;
n=length(tree_node);
flag_x=0;
flag_y=0;
for i= 1:n
) f9 D& g$ Y: i; Z" {5 |* E  P    if tree_node(i)==index_x
+ K% k6 O( l7 K0 Q; O7 i        flag_x=1;
    end
- h( w$ }5 a% T$ j" H/ D    if tree_node(i)==index_y
        flag_y=1;
* z5 a8 G# b2 l  _, ]    end
- }6 T; w/ h; b5 g' nend
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
  M9 h$ O5 M, y程序好像有问题吧：只是把权矩阵中的最小值一次加入到tree_border中，没有管是否已经联通所有的点，或者是否 ...

8 j" m, C- y  e& ~& x# U找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...