最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
* Q, [* [& v/ m8 e! f9 @6 la_copy=a;
for i= 1:n
+ x0 n  d: |2 n$ x2 S3 E  M    for j=i:n
9 G5 A3 m+ H9 z. ^4 k9 O' U/ v- o        a_copy(i,j)=inf;
    end
end
+ ?1 n; y0 z9 T0 ~. g2 ?5 f( ntree_martix=zeros(n,n);
; e% o6 G( D0 r+ t7 bcount=0;
) \9 G: d6 Z' D) E$ P2 l6 g
tree_node=zeros(2*n,1);
i=1;
% n) g" c2 j$ R# dwhile count<=n-2
    b=min(min(a_copy));
' P' X) p& A% i2 F4 f9 k& X    [index_x,index_y]=find(a_copy==b);
4 V/ x4 J# k: x: q& {0 V% K     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
* I& w9 o% \+ U; p0 x! x9 e1 w& Z& q( s     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
        continue;
/ T0 R/ N2 V5 H" {    end
    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;
5 n  {1 S% v/ X8 z. Q# [    a_copy(index_y,index_x)=inf;
   
9 v4 q" g& x! L6 p    count=count+1;
% s. Z( f9 ]4 b; `. @1 A( ^8 F: F   
% B) X( z5 Q+ O* Vend
1 s/ |* z6 Z9 H/ atree_border=tree_node;
6 m1 B7 M" M) z-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
+ Q6 i2 r) ^' ]2 nflag=0;
4 A% o; M' m" I) b: B0 }/ Z. m4 nn=length(tree_node);
flag_x=0;
flag_y=0;
+ Q: C0 j( A2 X3 c, zfor i= 1:n
    if tree_node(i)==index_x
$ P4 P1 \2 _3 _6 j        flag_x=1;
7 C$ H  t' W; O    end
/ H: f9 `" E4 X: u. b& L/ B) J    if tree_node(i)==index_y
5 f6 f# b# {# V- O0 C0 x. ]5 p        flag_y=1;
    end
0 R% L% K, \/ D: r0 V9 l) E$ H  Hend
, E' c# q7 x' t2 M' yif flag_x==1&&flag_y==1
: v* H6 u' M' }* A! i$ b    flag=1;
" s8 @( R, }/ E4 [end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

2 [& V- K4 P* H9 A- f" B2 @找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...