最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
5 V$ Z3 q7 K! Ffunction [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
a_copy=a;
9 a$ n9 p* ]( Y' J; |9 U  wfor i= 1:n
    for j=i:n
        a_copy(i,j)=inf;
    end
. j5 P) G6 n7 f/ @- {end
tree_martix=zeros(n,n);
count=0;
5 x8 X% }' r- w4 M8 w
tree_node=zeros(2*n,1);
i=1;
while count<=n-2
4 v9 C! ?* a, G& w# b1 V! @/ V    b=min(min(a_copy));
    [index_x,index_y]=find(a_copy==b);
6 d: D; z% w% T! K     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
* c9 g' P" k  `+ |     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
        continue;
) @5 @) K8 m$ x5 I( u. ?3 G+ n    end
, z, o: r, h" Q2 v    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
; T: L4 d8 B4 A, x$ e% [* A    i=i+2;
. U/ \4 o2 q6 |6 F    %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);
; ^4 B- ?& E6 K$ j9 ^2 O5 ]4 h    a_copy(index_x,index_y)=inf;
    a_copy(index_y,index_x)=inf;
   
" J: G" X3 c; F7 z  f' T9 c    count=count+1;
& r, `/ q& U" i( i3 |( q" O   
8 ]6 C. X7 t8 e0 k1 Pend
tree_border=tree_node;
-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
flag=0;
n=length(tree_node);
flag_x=0;
flag_y=0;
for i= 1:n
    if tree_node(i)==index_x
. {; _! x$ a8 |9 R' E( W        flag_x=1;
1 G% @& w: ~* I# X9 x  `/ T    end
    if tree_node(i)==index_y
        flag_y=1;
    end
2 C# R. Q2 p1 ^4 z, Vend
if flag_x==1&&flag_y==1
    flag=1;
2 r4 Q# j- ^8 q7 C, Yend

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

qluther 发表于 2010-8-15 12:41
" C+ }" W  R/ C; l' X/ p& G程序好像有问题吧：只是把权矩阵中的最小值一次加入到tree_border中，没有管是否已经联通所有的点，或者是否 ...

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...