最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
# D: p8 h5 n8 h% Nfunction [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
: Y) x  v! S9 m: f" {2 s0 Za_copy=a;
7 M- V' u  i0 e! [/ F7 o) H# Rfor i= 1:n
* I" N4 h' c& }3 o4 z" d/ L, T    for j=i:n
2 d. o# k0 A# U5 y        a_copy(i,j)=inf;
    end
5 L+ J+ P: A/ T1 iend
& h2 o, Q+ t; z2 g' etree_martix=zeros(n,n);
count=0;
9 v/ T2 j' [. X/ ]. l
tree_node=zeros(2*n,1);
# B! J- v* h" W6 b* oi=1;
while count<=n-2
    b=min(min(a_copy));
    [index_x,index_y]=find(a_copy==b);
( P3 E5 b; z4 c6 t6 w" g     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
& l/ [- o( I! w5 _        continue;
    end
, \3 q0 N: M- W9 \# |' x7 z# C( X    tree_node(i)=min(index_x);
; ~& i. f( b  _3 U6 V, N" z3 P; M/ D    tree_node(i+1)=min(index_y);
    i=i+2;
- g; R, e% r2 G% W    %a_copy(index_x,index_y)=inf;
# W% H  D2 r7 @& B# s9 I& Y# t& Z    %a_copy(index_y,index_x)=inf;
2 r2 U+ Q7 f* Q. h  o    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
    a_copy(index_x,index_y)=inf;
    a_copy(index_y,index_x)=inf;
   
2 R+ {$ T0 v( p) q    count=count+1;
3 i. K6 k( B4 `   
2 H. a/ c1 i' ~. `: O6 t' E, tend
" ]/ j' {3 P- K: ^) Wtree_border=tree_node;
% ?) c) y: _; a  n$ i-----------------------------
2 X' S8 K: \7 Q: S7 S0 Tfunction flag=node_judge(tree_node,index_x,index_y)
flag=0;
' p, e- \* Q( h: S* Z4 zn=length(tree_node);
flag_x=0;
flag_y=0;
) N8 \' k! ~. {+ h$ Rfor i= 1:n
' n( x) q! V0 V+ P" A1 _; o, y    if tree_node(i)==index_x
        flag_x=1;
    end
    if tree_node(i)==index_y
/ ~5 @' b3 Y$ h        flag_y=1;
    end
end
- c" b7 o: n, r/ y0 O( S' e8 g. {if flag_x==1&&flag_y==1
    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

/ c# D; V/ b" j" G% _( P% H: r找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...