最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
1 U0 m. Y& u, U* wfunction [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
) x9 N9 F# v7 q/ W: G/ F9 z! ga_copy=a;
. v, ^1 m4 c' h* c% T. `% ^for i= 1:n
    for j=i:n
+ L, w6 }+ n2 D+ a) O- y4 g        a_copy(i,j)=inf;
    end
; q5 |. Q3 R2 P$ K) n! W: kend
tree_martix=zeros(n,n);
count=0;

, ~! u2 y0 ]1 ^# f* N( B/ n) dtree_node=zeros(2*n,1);
8 n% B/ Q* s- G; ], n" vi=1;
2 m, I! n8 \( ^; i) i. i" {while count<=n-2
, e! q: P, P! M& s    b=min(min(a_copy));
5 S% X2 @: N9 ^' B3 [    [index_x,index_y]=find(a_copy==b);
+ A# v3 ^* l; f! f7 K' q! H     flag=node_judge(tree_node,index_x,index_y);
  C$ ?# G# o/ }2 z+ L0 }/ ~    if flag==1
1 {: W3 w8 j& ^# \7 \     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
        continue;
$ v/ N* ?' X  z4 w: s/ P1 ]    end
: A7 N% {* C* _$ M  x2 D    tree_node(i)=min(index_x);
/ h, K# \0 }7 O7 e+ W: M    tree_node(i+1)=min(index_y);
    i=i+2;
% u' \3 I& p$ y* l0 V1 X" G3 Y6 _6 u8 d    %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;
! S( a# U9 a* }2 q    a_copy(index_y,index_x)=inf;
$ \, e# X" @5 j9 ?) [/ m5 s   
    count=count+1;
; ~5 t& c$ b  y4 l" K& @+ O* N& m   
' Y3 W0 {, i/ K. uend
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;
* @; D4 k8 t) y/ lfor i= 1:n
. D  @& Y8 Y& _3 m    if tree_node(i)==index_x
        flag_x=1;
" V" Z& l' V% U* m    end
0 |3 s* p/ G1 x  S/ p( k7 ?* U    if tree_node(i)==index_y
        flag_y=1;
' _' F5 G/ q* v* a/ L: U    end
end
. s9 s% L# M$ w1 c6 c. [7 Qif flag_x==1&&flag_y==1
    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
) D& Y  D! K! Y

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...