最小数prim算法

水木年华zzu

求最小树的prim算法
# b( l. E0 Y2 S5 }) l! ?. |. a9 Y说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
" P% H7 V, j/ [* J, ^, p  X* on= size(a,1);
a_copy=a;
) p7 \" ^9 B: ]1 }" Zfor i= 1:n
! [5 q/ `2 `  _    for j=i:n
        a_copy(i,j)=inf;
" P, A: H9 b6 y1 v* v$ x8 n    end
end
4 k# u# `' _& O" Q5 @9 Xtree_martix=zeros(n,n);
  Q! G5 z. ~  e' L2 gcount=0;
" T4 ^; z5 Z0 h& S3 G
tree_node=zeros(2*n,1);
7 T+ f  t) ~9 s2 n6 i5 l* _i=1;
- Y2 K' B. |, v  \( P0 `while count<=n-2
    b=min(min(a_copy));
: I* y, q  h" p$ `5 u" j, b    [index_x,index_y]=find(a_copy==b);
! N% a" D. K$ `     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
. F" u1 q  O& C, A& J, Q1 @# t+ Q; G     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
        continue;
' e; U, _$ e" V0 `. F( T6 z    end
    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
    i=i+2;
: o3 \: y6 u' C' ~6 [+ Y    %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;
) v  ]/ d; W' Z4 h9 R    a_copy(index_y,index_x)=inf;
   
    count=count+1;
   
! g4 Z* I6 o2 }, x. J6 p/ K9 cend
7 N% Y* J4 ?9 W9 [+ btree_border=tree_node;
-----------------------------
$ n& n0 f5 c7 o( Q1 x0 Y& gfunction flag=node_judge(tree_node,index_x,index_y)
; C; M& W; g( ~+ {  Fflag=0;
% V1 J. c8 A4 D9 u2 @- w; vn=length(tree_node);
flag_x=0;
flag_y=0;
for i= 1:n
- F6 }6 O) N* ^0 a# h8 C7 \( i    if tree_node(i)==index_x
& c- I% a+ M6 g! p( f        flag_x=1;
0 T% |5 C6 N" j2 l$ V( V3 D) W1 \    end
# J9 u  y0 @" n( k# ]" a2 c. q5 q    if tree_node(i)==index_y
        flag_y=1;
    end
end
if flag_x==1&&flag_y==1
# ]! ]; o; E7 g    flag=1;
* X7 j$ k/ ^  a, p. y/ m# Y# Zend

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

6 \# J! h$ p$ W2 B, [! U+ e找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...