最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
a_copy=a;
for i= 1:n
; ?0 b' c3 j  D, `" s' u* U    for j=i:n
        a_copy(i,j)=inf;
3 d* ~. K) b% d4 M0 U    end
: x6 n0 d3 P& J# g) }! m5 hend
& [0 o5 ]3 O( j' O  Ctree_martix=zeros(n,n);
6 R: X5 v$ D4 t- P, T0 S3 L7 n( p: e9 zcount=0;

2 X* P" {, G( ^4 c5 v1 ttree_node=zeros(2*n,1);
i=1;
while count<=n-2
' s- n0 ^  _' w; q7 _    b=min(min(a_copy));
( ]- i4 Y" B0 Y. Z' u    [index_x,index_y]=find(a_copy==b);
2 ^! }  a+ C1 q. y# V8 f4 m     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
     a_copy(index_x,index_y)=inf;
' [* ]3 g2 B1 y" w2 i     a_copy(index_y,index_x)=inf;
/ D+ K; f7 H/ S' \! i        continue;
) X, Q$ M+ c/ o& A  j4 S    end
. a, _; n$ d* L- s. t. n    tree_node(i)=min(index_x);
# H* c5 w( [9 I3 S0 y  A    tree_node(i+1)=min(index_y);
    i=i+2;
    %a_copy(index_x,index_y)=inf;
    %a_copy(index_y,index_x)=inf;
9 J( F2 J8 c' H1 {& R5 L1 n) `9 Y    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
& g3 R' b' B8 C3 |; l    a_copy(index_x,index_y)=inf;
4 k) N- z' D  v5 i6 b    a_copy(index_y,index_x)=inf;
   
  M* l8 d/ m5 J" C& G7 I" ^    count=count+1;
. i5 K. t! M" |) L+ F   
end
tree_border=tree_node;
, C. M3 z* R, Q% q$ d" V+ T9 o-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
flag=0;
: R8 }" ^* `' k( _5 F! O( z6 z) @! Cn=length(tree_node);
" \1 v! M- j* r, G8 u, N) Pflag_x=0;
flag_y=0;
2 a* D/ M. b( Q% U4 }! ~for i= 1:n
+ x% k, L. N/ j& l0 o4 T, R0 S    if tree_node(i)==index_x
        flag_x=1;
    end
6 o  a6 @( d3 k7 _) l8 t    if tree_node(i)==index_y
* _" p8 `/ J. Q9 A! Z        flag_y=1;
    end
$ q4 g: v8 O2 ]! T/ P. t: oend
if flag_x==1&&flag_y==1
0 ~) p0 K& C5 \; ~8 X7 G    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...