最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
7 V0 C% M2 c2 b2 Rn= size(a,1);
  g: e1 W/ m! @8 p5 v0 Ga_copy=a;
for i= 1:n
    for j=i:n
9 I9 s6 v3 F, z        a_copy(i,j)=inf;
    end
end
3 r3 U4 u" j3 j. O6 Wtree_martix=zeros(n,n);
' p$ X0 }% f% k+ C& Dcount=0;
  d  C+ q% ^4 M7 I: e; U2 R
" q7 x7 }. ~" X( S' dtree_node=zeros(2*n,1);
' ?2 i, F6 w. A( V! V) e+ oi=1;
9 q, Q( u$ O3 y5 Swhile count<=n-2
    b=min(min(a_copy));
    [index_x,index_y]=find(a_copy==b);
     flag=node_judge(tree_node,index_x,index_y);
2 P: f# r7 `7 ^8 d4 h1 S    if flag==1
     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
        continue;
  G. D: `! ^1 J) e& q    end
1 k8 w) `# R' d/ r    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
    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);
    a_copy(index_x,index_y)=inf;
    a_copy(index_y,index_x)=inf;
   
    count=count+1;
   
end
tree_border=tree_node;
% E$ E% {2 w" O" b1 y. u$ a8 r-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
flag=0;
% T, U3 v4 \: }2 B" q) h, {- c9 un=length(tree_node);
flag_x=0;
flag_y=0;
: q% a, u! P( l2 K8 }for i= 1:n
    if tree_node(i)==index_x
        flag_x=1;
    end
    if tree_node(i)==index_y
$ {8 U; K  x8 G% d; T        flag_y=1;
; y( p. n8 ~+ I) x5 C- I) N- B, N    end
end
# M: c) F3 r* ]. I) r1 V6 Iif flag_x==1&&flag_y==1
8 \8 k" w9 ^2 u6 n) z8 z6 n9 D. J8 F. t    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
; y+ ?1 @  O$ H& h8 [& s

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...