最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
2 C0 A% ^1 `1 {4 [8 ~! l! Ofunction [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
a_copy=a;
for i= 1:n
$ ]3 M$ b$ Y' y) R/ w    for j=i:n
# g( d" [. {3 U, U" P+ y        a_copy(i,j)=inf;
# Y5 L: M: d# m9 N4 Z" l    end
end
$ D1 ?+ f3 ~# ?9 dtree_martix=zeros(n,n);
count=0;
& `4 f7 z3 R. i# i# k, U: A$ e
tree_node=zeros(2*n,1);
i=1;
while count<=n-2
    b=min(min(a_copy));
7 x; i6 s) N8 P8 k# M+ l" u    [index_x,index_y]=find(a_copy==b);
4 U7 h: |- p8 H7 B0 }     flag=node_judge(tree_node,index_x,index_y);
) z5 h7 c* D$ B    if flag==1
* k1 t2 \. T: W/ h     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
        continue;
    end
    tree_node(i)=min(index_x);
& r7 x& C5 G# i1 n$ Z" x6 D$ Z+ u    tree_node(i+1)=min(index_y);
    i=i+2;
# S8 R3 V% p+ {7 M$ u    %a_copy(index_x,index_y)=inf;
    %a_copy(index_y,index_x)=inf;
4 k7 s4 {7 D/ R! [2 R2 @    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;
, y7 N1 i  s" ]   
+ Y, ^/ B9 o% w+ I# d) e' U    count=count+1;
   
1 S/ d- b+ R% {! d$ b2 \+ bend
tree_border=tree_node;
-----------------------------
4 J  H9 |! L" W; w* {function flag=node_judge(tree_node,index_x,index_y)
flag=0;
7 `9 @7 W8 F$ {  G& T+ x$ P% Kn=length(tree_node);
flag_x=0;
  H9 k' s8 R# r3 {/ _" {flag_y=0;
for i= 1:n
    if tree_node(i)==index_x
" p/ Z4 E2 z# Z# s* j0 P6 e        flag_x=1;
4 C, ?* P: U3 Z$ l    end
3 g, F. N: \/ I+ t. [  ~+ t    if tree_node(i)==index_y
) w: q$ m3 _( [  }9 Q, i  O        flag_y=1;
* S! j* J' ]( s( {* `; c+ U7 b    end
end
" f0 }/ M1 |& Pif flag_x==1&&flag_y==1
1 ~/ @0 P5 g& r5 O3 x/ h- m3 P5 [    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
7 @  G, k% y4 l! k3 ?* u

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...