最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
0 ?: l1 z  q* @" F/ B) ifunction [tree_martix,tree_border]=min_tree(a)
' e! ]! }- O( g: H# o6 kn= size(a,1);
a_copy=a;
for i= 1:n
    for j=i:n
3 R) {* }  ^* y) D$ l0 B6 I        a_copy(i,j)=inf;
    end
end
/ O2 c# \1 [; B" c( rtree_martix=zeros(n,n);
1 d# i: s7 z2 M, V2 j% t) Acount=0;
( ]$ K$ v/ V! @2 ?' _
tree_node=zeros(2*n,1);
$ `4 Q  j- x) u: X& u; L+ |+ J) n8 Ei=1;
while count<=n-2
, d7 t3 _4 E" E    b=min(min(a_copy));
    [index_x,index_y]=find(a_copy==b);
     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
) }1 \. O; w& t4 K     a_copy(index_x,index_y)=inf;
( h' f' B/ o" J) q+ s. R     a_copy(index_y,index_x)=inf;
        continue;
' U/ V& T) u9 s9 e* Y1 I    end
    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
    i=i+2;
    %a_copy(index_x,index_y)=inf;
" [" t1 R' A% j    %a_copy(index_y,index_x)=inf;
0 }* a, S  M6 D# I  j+ H8 {- i    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
    a_copy(index_x,index_y)=inf;
  }2 U) D% U0 x  l    a_copy(index_y,index_x)=inf;
6 w* X: {% X& }; g, ^" h   
    count=count+1;
   
; V2 f9 R0 e) L- |end
tree_border=tree_node;
-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
& _- j0 ?  l# C* @1 vflag=0;
n=length(tree_node);
/ z; G* n: ~$ Y: t' c- z' |flag_x=0;
flag_y=0;
for i= 1:n
/ N8 p5 P. I% W, R$ S0 c5 [% A    if tree_node(i)==index_x
        flag_x=1;
3 q0 G. w: b# w8 O    end
2 x- s' e% ]  d  M) T) _, u    if tree_node(i)==index_y
        flag_y=1;
    end
end
# K8 N* F  Z3 ^9 Uif 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
* ~' T6 ~' M: T; C  z4 }" x! c程序好像有问题吧：只是把权矩阵中的最小值一次加入到tree_border中，没有管是否已经联通所有的点，或者是否 ...

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...