最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
7 j4 @; Y. I, V. Vfunction [tree_martix,tree_border]=min_tree(a)
2 U: F) h9 J% L. _n= size(a,1);
a_copy=a;
1 M. M" L. o1 Q! {for i= 1:n
    for j=i:n
3 k. H8 w' ?( Q/ X0 Y& ~        a_copy(i,j)=inf;
$ y+ [5 ?$ P3 x% f) n    end
) J+ l1 J0 P5 p! W: T% U% bend
6 m( `4 S3 W3 h7 C; B) r/ Ztree_martix=zeros(n,n);
/ c6 l. h% L$ i- l5 L8 hcount=0;

tree_node=zeros(2*n,1);
; i  l  {: e8 j$ ]: f; l  p) |i=1;
* n  Z" s/ J  P9 uwhile count<=n-2
    b=min(min(a_copy));
0 F/ f* Z* n9 P- A. E. i  i2 O" O9 n    [index_x,index_y]=find(a_copy==b);
     flag=node_judge(tree_node,index_x,index_y);
8 `. F+ t: [; W0 Q* ]# X& O5 z    if flag==1
     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
        continue;
: U) z+ M7 ?" y    end
    tree_node(i)=min(index_x);
. H  W  z* t! y$ g" b( p    tree_node(i+1)=min(index_y);
& ]9 J4 c3 S% X6 S3 ?" z' t    i=i+2;
+ p# t$ f5 N% o- h  [: q6 R    %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);
' y* @" g$ U( ~4 G    a_copy(index_x,index_y)=inf;
    a_copy(index_y,index_x)=inf;
# f1 n! C' M5 M9 w6 w6 I   
    count=count+1;
   
end
tree_border=tree_node;
+ b! d% n+ N1 \2 X9 D7 {-----------------------------
) d) W" C: \, Ofunction flag=node_judge(tree_node,index_x,index_y)
. E: m. g% d4 S7 y4 Kflag=0;
n=length(tree_node);
( N9 n- H) z- K3 ]; \; K. Rflag_x=0;
flag_y=0;
for i= 1:n
, n  {. B' n8 h* O$ G    if tree_node(i)==index_x
6 ?0 E, l5 ]6 t        flag_x=1;
- L: Z$ t) @; g9 r3 Z6 L- G1 f    end
    if tree_node(i)==index_y
        flag_y=1;
  u: W7 V, v% H    end
end
8 C2 D! |- r4 L# w4 L  Oif flag_x==1&&flag_y==1
    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
6 v# k$ t* M# G$ H3 C4 i

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...