最小数prim算法

水木年华zzu

求最小树的prim算法
: g8 q! q( Q2 X- Q! O( V. U: y& {说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
3 T# ]' C5 `4 ~# {7 ma_copy=a;
for i= 1:n
; T& w3 {. Q* O- o    for j=i:n
; {/ z( f( ?7 c& J, f; \+ C        a_copy(i,j)=inf;
* f/ B. M3 d. z" v% q/ O# a8 X    end
end
tree_martix=zeros(n,n);
! D7 x. q2 @8 }. m( p9 x8 Zcount=0;

# b+ U) B7 W. R7 w% stree_node=zeros(2*n,1);
i=1;
$ u0 I. N* X$ L* \; `while count<=n-2
  {0 R" a+ |& @! o. Y& p    b=min(min(a_copy));
/ A+ n. t- \; K" P    [index_x,index_y]=find(a_copy==b);
     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
     a_copy(index_x,index_y)=inf;
* p' D! O$ j. l  \* P     a_copy(index_y,index_x)=inf;
        continue;
) _0 L; r" L+ k$ s    end
    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
7 \' _& o5 g" X7 H    i=i+2;
    %a_copy(index_x,index_y)=inf;
! }3 }/ i% E- o8 J( z9 Y    %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;
   
) n+ G- g, z, e, N- U* U    count=count+1;
4 N) [- t# O+ b, U& w% p% R   
end
tree_border=tree_node;
-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
3 R( m/ w$ V  g; u8 J' P- yflag=0;
n=length(tree_node);
! h8 i* C1 n" p5 k7 Z! T# d/ `flag_x=0;
flag_y=0;
for i= 1:n
    if tree_node(i)==index_x
' o. L, s/ \" }, y$ |3 s4 _8 a2 y* s        flag_x=1;
/ N( j# h+ f$ w5 ]! x1 a( Q    end
    if tree_node(i)==index_y
8 N# X+ W* A. t" ?( Z9 }( k( n/ v        flag_y=1;
    end
end
+ e5 P7 Y/ _0 e7 N- l& vif flag_x==1&&flag_y==1
4 ]. b  s  ]5 z0 G" q/ J    flag=1;
. t  @% E; H% d) Q  x* Jend

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

qluther 发表于 2010-8-15 12:41
  M0 ~) \( y) _' p0 O9 D* M程序好像有问题吧：只是把权矩阵中的最小值一次加入到tree_border中，没有管是否已经联通所有的点，或者是否 ...

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...