最小数prim算法

水木年华zzu

求最小树的prim算法
( F* ^+ m7 u, r1 a/ E5 q% T: B: h说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
6 B5 m$ ?" i: }% On= size(a,1);
! P/ A8 a/ n4 wa_copy=a;
for i= 1:n
    for j=i:n
        a_copy(i,j)=inf;
3 F4 p! h, T' B* m( k    end
end
8 |% `3 H: E& S; ^8 _7 C' J. [9 i% A. c& Jtree_martix=zeros(n,n);
count=0;

) |9 F+ A8 l6 W! Jtree_node=zeros(2*n,1);
i=1;
5 b- X4 ^* j6 G, D/ Pwhile count<=n-2
; T; n$ v6 l' o( u! u    b=min(min(a_copy));
    [index_x,index_y]=find(a_copy==b);
% h9 G4 d( R' F: O7 l" e5 {. ?     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;
9 Y9 f8 Q. [6 i' a        continue;
7 V  Z! K$ x5 b; @; W+ p6 Q. {    end
/ S) L* l" X1 e: [  l9 T1 z5 \    tree_node(i)=min(index_x);
7 E; y" |/ }3 q( J$ @) J, q    tree_node(i+1)=min(index_y);
  V- v! a) d5 n5 O% n; m6 x- Y# C    i=i+2;
- O# D& R  [6 i6 }6 }    %a_copy(index_x,index_y)=inf;
# P: U0 X1 {. K) D( T    %a_copy(index_y,index_x)=inf;
4 j/ ?5 R! ]# v, d# }    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;
% p9 z  V) ]& S$ H4 K: T   
    count=count+1;
   
0 P7 q+ a5 @  w  \9 X) ^  S- xend
tree_border=tree_node;
-----------------------------
+ n6 l& D$ S/ Z4 f2 @6 Wfunction flag=node_judge(tree_node,index_x,index_y)
, r% G5 Y, V% I& Wflag=0;
n=length(tree_node);
, P6 S5 r: Z! e" T8 p8 uflag_x=0;
flag_y=0;
8 R6 W7 W$ j. g" K; X( L$ G) Q( bfor i= 1:n
    if tree_node(i)==index_x
        flag_x=1;
5 j2 p1 I+ A' `# J6 y    end
    if tree_node(i)==index_y
        flag_y=1;
    end
4 p; o& f  A$ e% W  Tend
if flag_x==1&&flag_y==1
4 c0 E1 o) S& N. U+ V/ Q    flag=1;
( `0 I- H' T1 A# tend

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
$ c& L& I. }. m5 z$ {- f

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

qluther 发表于 2010-8-15 12:41
. I3 A( W( y2 ^9 K4 R4 ?" ?2 V: s程序好像有问题吧：只是把权矩阵中的最小值一次加入到tree_border中，没有管是否已经联通所有的点，或者是否 ...

; v5 Z2 v/ o7 c; [9 {- v$ U找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...