最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
. _; P# p1 {8 }+ E: Wfunction [tree_martix,tree_border]=min_tree(a)
% [6 n9 J6 }9 l. c8 X# mn= size(a,1);
% B2 q. N' j1 X% G$ Ca_copy=a;
for i= 1:n
    for j=i:n
        a_copy(i,j)=inf;
    end
9 D) P2 A+ X+ [. bend
. V  [) X5 f+ T$ b9 S( ltree_martix=zeros(n,n);
9 @8 @" y; E- x8 m) @0 ecount=0;

: _- n. _: z; H, btree_node=zeros(2*n,1);
i=1;
* M( j* i8 l% T7 y3 Q0 x" ~while count<=n-2
    b=min(min(a_copy));
    [index_x,index_y]=find(a_copy==b);
' }9 h! x% c8 u# P/ o- M, S+ x0 k     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
2 e5 V$ z7 P4 ~# I9 B# P& j# I' |# z     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
        continue;
% A( R! u- `9 b9 B+ s6 p) n    end
    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
    i=i+2;
) I8 {/ Z8 {: _4 F) ]" ?  B) [- P    %a_copy(index_x,index_y)=inf;
    %a_copy(index_y,index_x)=inf;
; y, Z0 ~) x1 x# R! K( r    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
) v2 `4 ~* ~' |) F5 I2 b& E+ ^    a_copy(index_x,index_y)=inf;
1 i" g0 M7 D) E    a_copy(index_y,index_x)=inf;
   
9 u- q! i$ \( S+ x4 V1 w6 u    count=count+1;
0 h, n) @$ d7 t$ S$ r# v   
! {+ m0 d, y' f! o) u  e1 W- N  Nend
8 T7 R. w0 f9 ?6 O$ Ltree_border=tree_node;
& B5 [  ]1 y, z-----------------------------
3 j. X! w( Y8 o5 \& ?1 z4 Xfunction flag=node_judge(tree_node,index_x,index_y)
flag=0;
n=length(tree_node);
flag_x=0;
flag_y=0;
for i= 1:n
    if tree_node(i)==index_x
        flag_x=1;
    end
, t* `, C0 `, Y( Y8 {    if tree_node(i)==index_y
2 q/ X" X8 e1 a! s: j2 e1 N( m        flag_y=1;
/ |0 N9 T; I& K! e    end
  M1 N/ o( v7 tend
; W2 }0 A! {1 H& K4 ]# Hif flag_x==1&&flag_y==1
    flag=1;
: U" P, y& w4 Z! O0 {" ^& o( w3 Lend

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
; S4 J: o$ T) a; `. M

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

" |" S7 A8 R% X. \. m' K找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...