最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
6 ?5 ^/ Z. U( X$ i+ R8 h# W+ dn= size(a,1);
. b. Y) b( E3 s' Ga_copy=a;
for i= 1:n
    for j=i:n
        a_copy(i,j)=inf;
$ K9 P9 X- }- `, T    end
5 @9 V) i1 R9 a# u" h. A" Iend
* R2 i' Y% i5 a/ t! E9 itree_martix=zeros(n,n);
count=0;
* u- f' @; y9 d/ A6 f1 j
+ d7 r  @! d" j  U% Jtree_node=zeros(2*n,1);
i=1;
while count<=n-2
    b=min(min(a_copy));
8 j( S# H( a3 y2 g! f' L1 p    [index_x,index_y]=find(a_copy==b);
8 |2 n! r8 |0 U0 A, i     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
# ^+ u5 M  [6 e     a_copy(index_x,index_y)=inf;
0 C& R. _$ B* M     a_copy(index_y,index_x)=inf;
  e4 V. B9 o8 q5 O. n; d/ L& a        continue;
) M" d0 f, s4 ]3 o7 s6 e: a/ J    end
    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
    i=i+2;
( e1 b6 p9 [% H; S    %a_copy(index_x,index_y)=inf;
, F7 b0 B" y  _5 i6 A2 L1 i    %a_copy(index_y,index_x)=inf;
    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
& `) v- h7 y8 V8 k& Z4 k/ m    a_copy(index_x,index_y)=inf;
" m! |0 g9 c! m3 K- I% I    a_copy(index_y,index_x)=inf;
   
9 G' p' Q8 r" x, p. f5 h& j    count=count+1;
' c1 h3 j4 Q" o1 S- `   
0 f$ r4 V# d4 {7 N2 V, bend
tree_border=tree_node;
-----------------------------
: k' n) \/ f  |% [$ s, w' Cfunction flag=node_judge(tree_node,index_x,index_y)
8 ]/ l8 d- x% F- c# p7 Q: }- hflag=0;
8 d1 p. @) V+ H! xn=length(tree_node);
3 Z0 f. t0 t, p8 }8 H# Aflag_x=0;
flag_y=0;
for i= 1:n
* i' I8 r3 o( S8 {, n9 Y7 s    if tree_node(i)==index_x
; H3 I; H$ Z' ^; ?8 Q0 c0 |$ c# ^% Z4 e        flag_x=1;
* n1 ~- H" [& |5 J" e" s4 T. ]    end
    if tree_node(i)==index_y
        flag_y=1;
" ~+ J% S- T. E8 |& ]9 I' a    end
end
if flag_x==1&&flag_y==1
& I( z9 e4 g5 f" A    flag=1;
end

朱鑫鑫

...

小叮当1016

谢谢分享程序～

水木年华zzu

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

& `. k$ I* G7 c8 I' m( R. x找几个矩阵验算下就行了

效忠w手掌

谢谢分享程序的人，

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

qluther

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

qluther

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

zhangkay

谢谢分享程序～

大笨象

谢谢分享程序～