最小数prim算法

水木年华zzu

求最小树的prim算法
! ^" b, E2 }7 e7 {1 c7 c说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
! ?% t+ j( s5 H" g+ ta_copy=a;
for i= 1:n
" v2 g( @9 X) t( E7 l( m5 k    for j=i:n
        a_copy(i,j)=inf;
' b- _" q% d7 }3 c3 M' ?2 }    end
end
tree_martix=zeros(n,n);
! P, ?/ ~2 \5 q; x$ S; E% v' Vcount=0;
+ b; \; g- ^" l5 x6 Q- d/ @
: k; ^7 X1 d2 s2 K2 ktree_node=zeros(2*n,1);
% Z8 \. H1 a$ M% }+ t6 j* ~i=1;
3 ?- _! N5 _9 K. x3 Rwhile count<=n-2
    b=min(min(a_copy));
& P2 |6 R( _  B  I; {, G    [index_x,index_y]=find(a_copy==b);
  W" B! u3 E" X3 t. s6 O     flag=node_judge(tree_node,index_x,index_y);
9 n2 S2 u: b$ E, K    if flag==1
     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
        continue;
# i& a4 R7 H+ S: q    end
+ y' J9 {/ l( S! Y/ g    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
/ ]% ?: `' a4 j/ h  ~    i=i+2;
    %a_copy(index_x,index_y)=inf;
4 m* O7 ]4 B4 v2 V    %a_copy(index_y,index_x)=inf;
, k0 D& s5 W8 n7 q3 f    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;
   
    count=count+1;
5 I" k# U- k) g+ o3 N/ M4 i   
end
! @0 P, _5 {2 S; wtree_border=tree_node;
. B) V% k/ b( u. T1 P$ m( U-----------------------------
7 e' j, n4 h5 |# N5 R0 afunction flag=node_judge(tree_node,index_x,index_y)
! d' q; Y0 L; C; W( [5 ]- T8 O3 Xflag=0;
n=length(tree_node);
) C& y' r. F  @, Gflag_x=0;
flag_y=0;
( e/ Z1 B" \8 [( jfor i= 1:n
" I" F5 ?- j% u) [    if tree_node(i)==index_x
        flag_x=1;
    end
+ n; x+ q7 ~; P8 C5 a    if tree_node(i)==index_y
        flag_y=1;
% T# @5 `" F9 [& ?7 ~4 L2 A: J  b5 p    end
5 h, a! Y. D+ aend
if flag_x==1&&flag_y==1
    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
, P* u3 T1 u. i/ z8 D

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...