最小数prim算法

水木年华zzu

求最小树的prim算法
% \! I% v% G9 W- k8 s) H! s7 k说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
( `9 U9 N) Z, e1 h! Z& Dfunction [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
a_copy=a;
for i= 1:n
    for j=i:n
        a_copy(i,j)=inf;
4 Z# w6 D( c. \  ?# ^: \    end
; z- j" m( q" M5 X  oend
4 |( w( F3 n0 V" E/ e) ytree_martix=zeros(n,n);
- Z9 F( a; M& Gcount=0;
9 ]2 u( W! [* q; Z/ o
tree_node=zeros(2*n,1);
4 M5 ~  J) o) C% _8 C/ k# ?' g2 O) Yi=1;
5 C6 I2 O& h2 o1 `& C- u# o- l5 `# Xwhile count<=n-2
    b=min(min(a_copy));
    [index_x,index_y]=find(a_copy==b);
  G( c1 ^( B9 d  U( {" V# Q- O     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
     a_copy(index_x,index_y)=inf;
& d9 h3 o( g9 S7 k$ Y7 u, a! f     a_copy(index_y,index_x)=inf;
# j8 M+ H) ], b! z" @* p; \! U        continue;
    end
    tree_node(i)=min(index_x);
! F! W3 D6 C7 U    tree_node(i+1)=min(index_y);
1 f% {1 }+ _3 h! C    i=i+2;
    %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);
; V3 g: {: |/ N1 _# F9 ^) e4 e+ h% j    a_copy(index_x,index_y)=inf;
    a_copy(index_y,index_x)=inf;
   
  Z! {, p, g" [+ v$ h4 E    count=count+1;
   
' u2 o4 R4 X6 w' s; Dend
! r% T8 C6 n) }; gtree_border=tree_node;
-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
  C8 _  V4 M2 ~7 t2 i" |, Wflag=0;
n=length(tree_node);
$ `+ V( x; K7 A5 x6 e$ h# Dflag_x=0;
flag_y=0;
for i= 1:n
    if tree_node(i)==index_x
+ ~& N* j6 I7 r* Q        flag_x=1;
    end
    if tree_node(i)==index_y
- B8 D* _& ^' k, ~9 B        flag_y=1;
    end
3 q3 V6 r2 V, g' Z0 Pend
8 r* M; q& ~. l) h5 ^if flag_x==1&&flag_y==1
$ G  P* Q6 V! `+ h4 w    flag=1;
& o( f" u; b' K, Kend

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

# u8 J: A4 ?6 U6 j0 C, c* p找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...