最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
/ O! J- b* C1 X5 Z7 s- Y; [& Jfunction [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
' C( J$ T) ]) Ca_copy=a;
for i= 1:n
0 W& n, M; l! |+ f% I; f: {9 Z) {    for j=i:n
1 e( ~6 q; ]- h( j; S6 N        a_copy(i,j)=inf;
    end
end
tree_martix=zeros(n,n);
count=0;

$ f7 y: h, Y$ V+ m" @tree_node=zeros(2*n,1);
  l% r1 b7 r1 I9 G5 C* I) |i=1;
5 p8 q, H* k) s) R: _7 q# Uwhile count<=n-2
+ U3 X' \( ]. b- ]! d! t4 y: L, ^    b=min(min(a_copy));
( Q$ N+ B, q7 r4 i$ ^. }    [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;
     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;
6 g0 A* J. o" N- n/ C. g    %a_copy(index_y,index_x)=inf;
    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
# r7 M( C" i* A' f    a_copy(index_x,index_y)=inf;
    a_copy(index_y,index_x)=inf;
   
    count=count+1;
   
end
tree_border=tree_node;
; l4 d* M% ^% v-----------------------------
! Y+ P# }% U9 w7 f' q0 |function flag=node_judge(tree_node,index_x,index_y)
; I' I; b& X# W7 S1 g' y( \* ?+ Qflag=0;
8 D( @! k4 K2 Tn=length(tree_node);
  S0 w$ W, U  F, g; W) qflag_x=0;
8 `" q! B  p0 @9 @! a* a2 F- hflag_y=0;
4 l; W8 L/ p5 O5 R- ]for i= 1:n
    if tree_node(i)==index_x
3 I" g, k( o6 u5 N/ a: e2 ^        flag_x=1;
) F9 S( W( \8 c% M8 c8 X7 q    end
    if tree_node(i)==index_y
        flag_y=1;
    end
: P" D# o( m: H  send
  t6 E$ ^; g3 L8 j7 [+ \8 P- Uif flag_x==1&&flag_y==1
    flag=1;
end

朱鑫鑫

...

小叮当1016

谢谢分享程序～

水木年华zzu

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

3 t: d* E9 s9 Q5 D找几个矩阵验算下就行了

效忠w手掌

谢谢分享程序的人，

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

qluther

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

qluther

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

zhangkay

谢谢分享程序～
. W- i7 U% j# y2 ~

大笨象

谢谢分享程序～