最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
7 N+ N7 g# M( R) S* Sn= size(a,1);
a_copy=a;
; d8 \6 w# w0 a! Mfor i= 1:n
    for j=i:n
, B% l$ i6 i6 Z4 ]        a_copy(i,j)=inf;
    end
: i& G* Z2 k$ gend
tree_martix=zeros(n,n);
count=0;

- Q3 Z# l8 \7 E0 x0 p4 F0 ^, E0 p$ Vtree_node=zeros(2*n,1);
3 ^/ Q9 L6 s5 Wi=1;
while count<=n-2
3 G; w- ^  d1 ]4 s& V& ~- O9 H    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;
     a_copy(index_y,index_x)=inf;
        continue;
    end
% D% O" N- W  H    tree_node(i)=min(index_x);
7 h+ |" {, _* h+ l8 @' B4 [    tree_node(i+1)=min(index_y);
4 P* t# y  h( m9 }* q    i=i+2;
    %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);
+ W3 Z7 J. W+ M2 N    a_copy(index_x,index_y)=inf;
5 i2 A# G7 ~% K1 ~- T( @  v    a_copy(index_y,index_x)=inf;
5 f, N8 P. w: J# O9 G   
. f0 k* a6 {+ D. V    count=count+1;
   
7 Q6 n0 |( o: Iend
) u, Y( ?* T  v3 C" Htree_border=tree_node;
-----------------------------
; o  t0 m* P3 W" D5 Sfunction flag=node_judge(tree_node,index_x,index_y)
flag=0;
n=length(tree_node);
flag_x=0;
flag_y=0;
" c  m  m" y6 P# Rfor i= 1:n
# V1 I2 m& Y4 `7 ~' {0 L    if tree_node(i)==index_x
% c8 ~1 V( H" Q0 O& s        flag_x=1;
    end
, i9 ?, g) w& d! Y9 x  ^    if tree_node(i)==index_y
        flag_y=1;
    end
end
if flag_x==1&&flag_y==1
7 y3 E, |" n! y' l( M    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...