最小数prim算法

水木年华zzu

求最小树的prim算法
7 L+ j$ S% x+ Y" W% b  Z- S# d说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
2 v5 R/ K" r7 H* G" kfunction [tree_martix,tree_border]=min_tree(a)
' _  @4 S9 B5 c1 |4 E! i2 }n= size(a,1);
5 p# y% ~2 T7 A8 W" oa_copy=a;
for i= 1:n
    for j=i:n
        a_copy(i,j)=inf;
    end
" H8 J) O0 q7 @end
( u+ o' }1 [7 o0 g- g7 \tree_martix=zeros(n,n);
count=0;

tree_node=zeros(2*n,1);
! [# {5 C( G6 Z# z. }% f1 Ji=1;
( q" _' o5 p1 F0 D6 I/ `. uwhile count<=n-2
% H' i  ]. o( L1 ?* x1 V/ J    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
     a_copy(index_x,index_y)=inf;
8 h& R% \4 _$ B7 ]& F' n6 a8 u7 T     a_copy(index_y,index_x)=inf;
# ^5 B- Y2 L: }+ H; T) C' v        continue;
    end
    tree_node(i)=min(index_x);
: t7 O5 U8 D! e3 ?3 i    tree_node(i+1)=min(index_y);
    i=i+2;
; P3 N/ @: X/ P. M! z2 j# i    %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;
) Q+ U3 e$ d" m( E0 g, J$ V3 k    a_copy(index_y,index_x)=inf;
) L8 V; f7 X. d   
: Q7 d% V8 ~9 [: _0 M% D2 m& Y+ R6 g    count=count+1;
  t/ H: X( Z! C, _  g   
3 i) Q3 T: x0 ~5 c" i7 B; `2 ]' z; iend
tree_border=tree_node;
' ^5 r# r( j  S' {# d-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
8 r5 p4 }" A1 i2 \' Vflag=0;
3 U, F# d& ]9 a2 ~9 n8 fn=length(tree_node);
  X- X. C, {& q: x+ |flag_x=0;
flag_y=0;
: f5 o: I/ _) X. T1 k7 Y+ Ffor i= 1:n
    if tree_node(i)==index_x
  ^, j4 v' [4 S" o- Q1 P" V        flag_x=1;
    end
    if tree_node(i)==index_y
        flag_y=1;
( y6 R/ w, e6 l: s/ _( y3 V' K. F    end
end
) r, n4 A. t: b3 `if flag_x==1&&flag_y==1
    flag=1;
9 ^  Z( }) `) z0 N- send

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

! X$ P! g/ t. [3 L' F- I) q找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...