最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
4 H" \& n- x, C) un= size(a,1);
$ w3 |" I+ a, wa_copy=a;
  J! C8 l3 i( S8 }- bfor i= 1:n
: y4 T5 {7 I* Y4 t* f    for j=i:n
        a_copy(i,j)=inf;
    end
end
tree_martix=zeros(n,n);
count=0;

3 p8 ?: `8 y. w" w0 l& p- jtree_node=zeros(2*n,1);
0 z! Z2 @. v0 @5 Bi=1;
+ I, i# A" i' ]9 f8 T# e! hwhile count<=n-2
    b=min(min(a_copy));
" w! N5 B- i7 U0 m2 z+ Z    [index_x,index_y]=find(a_copy==b);
' c) y- I% I! I% |     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
. K. O3 q+ b  S/ f     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
        continue;
    end
2 K: `( O/ L4 z8 c' W    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
    i=i+2;
& U, U3 @: z% m) G/ C: P4 i    %a_copy(index_x,index_y)=inf;
' z: x+ d, d/ p  ~: L. _( ^    %a_copy(index_y,index_x)=inf;
    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
- S* }. i* E. i4 i3 x; y    a_copy(index_x,index_y)=inf;
' {* m$ i. {5 C" q2 V! v8 A    a_copy(index_y,index_x)=inf;
& c2 e8 _0 f3 T& \' z   
  J& [* F7 `4 J; U% A& T& k    count=count+1;
   
end
. c2 i9 W8 l! v+ z* c  _: V- ~0 i- xtree_border=tree_node;
-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
  f% s9 h+ `: v. }! Uflag=0;
! H$ [$ s& i0 Kn=length(tree_node);
* o' m5 Q7 F) Iflag_x=0;
flag_y=0;
for i= 1:n
    if tree_node(i)==index_x
& p- q( k2 r- _" U5 c4 f        flag_x=1;
    end
7 A7 y& w0 O% V* _2 O6 z    if tree_node(i)==index_y
$ D+ Q' u2 S1 P6 P) t: d1 ?        flag_y=1;
1 s) W3 `3 j3 J- ]7 @& n    end
5 n9 t! B2 A, G1 bend
* N' b8 {9 d! e. Q* V+ h5 Kif flag_x==1&&flag_y==1
    flag=1;
6 S- ^9 O, |+ R/ l# Hend

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
  Y7 t' ~4 t& l0 {/ ^( o- y

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...