最小数prim算法

水木年华zzu

求最小树的prim算法
& y# L' k' W9 s7 @说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
; t8 p% N* A: [8 ]! X9 Z; ]function [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
a_copy=a;
for i= 1:n
    for j=i:n
3 P! B+ `+ j/ Y: t        a_copy(i,j)=inf;
    end
1 t  d5 f6 c( Z& A: O3 @6 k1 zend
3 q" d) X- X2 c+ H9 k# qtree_martix=zeros(n,n);
1 r# k2 b, ~* J  J2 k$ Scount=0;
" c$ {- i" D" o9 X: c6 r
tree_node=zeros(2*n,1);
- S' f; v; S# Ri=1;
while 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);
    if flag==1
     a_copy(index_x,index_y)=inf;
2 P3 a7 Z/ b$ w8 m  |) m. D     a_copy(index_y,index_x)=inf;
        continue;
3 e8 {, k' g$ s    end
$ s1 q" L4 v/ E" ]1 B    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
8 R/ O: Z3 l6 {- n    i=i+2;
    %a_copy(index_x,index_y)=inf;
  a% X2 _7 d& X  _    %a_copy(index_y,index_x)=inf;
    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
  s2 j( c  C8 l. S/ i! p. r    a_copy(index_x,index_y)=inf;
( ~! A, _9 p* ?  @    a_copy(index_y,index_x)=inf;
   
0 Z/ }$ ], r, o! B: k6 L( [) Q    count=count+1;
( c: l) L1 R5 F& o1 M   
7 t' k/ z5 }, Q4 V( [+ Q& ?5 ]) \end
tree_border=tree_node;
-----------------------------
8 E" }4 v, ]+ J/ w7 L& B3 afunction flag=node_judge(tree_node,index_x,index_y)
flag=0;
n=length(tree_node);
7 T; D6 M9 z* T. j" T! o( J3 \flag_x=0;
) T0 {; z# \- Bflag_y=0;
+ c. p, H  a% z8 |for i= 1:n
    if tree_node(i)==index_x
8 Q6 b6 p. ]$ E' {, p        flag_x=1;
& A) B# z. b# w2 U! }! b4 p$ \    end
. r0 H' S! }% K6 k0 l: l1 _7 o    if tree_node(i)==index_y
        flag_y=1;
    end
end
: j2 M: S9 A7 d% F- iif flag_x==1&&flag_y==1
    flag=1;
9 g2 ]2 P; m) R0 i. _end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
! w3 E- f2 p' _( C; p

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

qluther 发表于 2010-8-15 12:41
. C& L) @0 m6 z' j5 b* X4 t程序好像有问题吧：只是把权矩阵中的最小值一次加入到tree_border中，没有管是否已经联通所有的点，或者是否 ...

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...