最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
+ ?9 L9 Z3 B/ @5 n6 ha_copy=a;
2 P( ^- D& i9 ?for i= 1:n
    for j=i:n
        a_copy(i,j)=inf;
    end
& F% r- ~$ U/ ~0 W) jend
tree_martix=zeros(n,n);
, B, B$ F1 z- B0 G' l7 E9 z3 R- Ecount=0;
" B$ {. u' ~+ l# |
tree_node=zeros(2*n,1);
) B& j0 ?% _7 W) }: N* Oi=1;
, o$ }! |! w/ I# D, swhile count<=n-2
7 Y- ]2 G# n$ M    b=min(min(a_copy));
) L: ~" y6 J; }    [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;
     a_copy(index_y,index_x)=inf;
: x3 @6 p6 O8 \# e% @4 O% K2 }        continue;
    end
+ F; z, Y7 Q) b9 b3 ]. c    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
    i=i+2;
4 J4 x- }) |* \" y& A    %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);
5 \" J/ K4 |3 j( [0 X    a_copy(index_x,index_y)=inf;
; }" b8 w, m: \$ ]  C    a_copy(index_y,index_x)=inf;
/ |: c3 O8 n0 D* g8 |0 f   
    count=count+1;
   
: o8 X3 _" A5 Qend
; k6 |' y& ]: Q) @8 Q- Ptree_border=tree_node;
; n+ y  @& [2 L1 W* d  ^$ a6 {-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
flag=0;
n=length(tree_node);
flag_x=0;
flag_y=0;
for i= 1:n
0 I. t2 h3 L' c) g& u1 x    if tree_node(i)==index_x
        flag_x=1;
    end
% Q: Q* w7 M( C' z1 c    if tree_node(i)==index_y
1 d. l1 R% p0 A: q        flag_y=1;
$ j1 F0 V2 S0 }) y4 W& V% }    end
end
# N) k% C/ z  _+ B, w; _: Pif flag_x==1&&flag_y==1
8 J% H# \5 |4 _- i    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

6 o% d( R/ D3 R) U( |9 n找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...