最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
1 }7 Y8 p6 n% f8 J; Fn= size(a,1);
a_copy=a;
* @, j) y0 c' @& X3 ^* tfor i= 1:n
    for j=i:n
9 _( }, p1 c* O        a_copy(i,j)=inf;
    end
# H; J* B5 [* i' Send
tree_martix=zeros(n,n);
count=0;
5 t1 |9 q' i; A! ]' V4 Q$ y4 b
$ I: F" ^. n( R9 x  Dtree_node=zeros(2*n,1);
i=1;
! {4 ^( p% S4 I/ X' u7 rwhile count<=n-2
    b=min(min(a_copy));
2 `6 {4 p$ f' d3 k' v    [index_x,index_y]=find(a_copy==b);
7 a- i. R3 U- l6 I  w& J3 v     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
     a_copy(index_x,index_y)=inf;
4 B( b- C( j% X2 Y7 F9 J     a_copy(index_y,index_x)=inf;
        continue;
    end
    tree_node(i)=min(index_x);
) D" c  _8 V4 E( `3 w1 r- Y/ x" P    tree_node(i+1)=min(index_y);
5 w2 L1 k7 o  W) v2 J) f' H    i=i+2;
    %a_copy(index_x,index_y)=inf;
8 f2 P8 C2 z3 T1 t    %a_copy(index_y,index_x)=inf;
7 j1 b( l; P$ ]7 U4 }    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
) i# Y: s  l7 h# x, N# _+ G    a_copy(index_x,index_y)=inf;
0 a- N; J  I0 @1 M* J    a_copy(index_y,index_x)=inf;
0 \8 ?- f! [- D. g9 b8 {   
    count=count+1;
. z1 }) D# |, F: @# f3 U$ ~1 x3 H   
( ?8 j. x& e  `) b7 g5 ~end
tree_border=tree_node;
2 l2 n/ |# I8 g+ {1 ]-----------------------------
9 F7 I4 t1 a* m8 n: U9 efunction flag=node_judge(tree_node,index_x,index_y)
flag=0;
1 L- d9 I' z, l: H4 I* Un=length(tree_node);
flag_x=0;
% z. c; i2 v1 n: v% v5 O' a- w* ~/ Uflag_y=0;
for i= 1:n
    if tree_node(i)==index_x
; A& r" [) Z. I- d2 J0 I7 _        flag_x=1;
    end
    if tree_node(i)==index_y
        flag_y=1;
  t3 o+ b5 i3 W8 u, g    end
end
if flag_x==1&&flag_y==1
    flag=1;
! l2 U. x( |& B  U) F* rend

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

! C% h, w; h# e找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...