最小数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
( N2 M$ I6 A/ y8 j* ^    for j=i:n
' V* u! k9 ]: M) Z# Y$ B. U2 {        a_copy(i,j)=inf;
3 t+ a% _: C7 P! C; X    end
8 b" \0 x$ [) H1 P) Lend
tree_martix=zeros(n,n);
. [  H0 {6 |& F' G- ecount=0;

2 U% y$ w4 b% Y9 J# G" T3 atree_node=zeros(2*n,1);
2 z0 N; \; }+ F, Wi=1;
while count<=n-2
" i1 @1 V/ n* K' F' f# l! m) l# x    b=min(min(a_copy));
    [index_x,index_y]=find(a_copy==b);
     flag=node_judge(tree_node,index_x,index_y);
4 i# N9 y! r1 ?    if flag==1
     a_copy(index_x,index_y)=inf;
: y% h: M3 N/ |- G! A$ }5 `     a_copy(index_y,index_x)=inf;
% \& z# A3 I, _& i4 Z8 A        continue;
9 ~; C" r+ A6 z. G" V7 O    end
    tree_node(i)=min(index_x);
4 Q7 W8 ?1 D1 Q9 Q% F    tree_node(i+1)=min(index_y);
    i=i+2;
: ^, Y0 [: X% e- J    %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);
* m9 S2 u% q% q# y    a_copy(index_x,index_y)=inf;
' O! Y( v0 C. j& I0 q4 E: Y2 G    a_copy(index_y,index_x)=inf;
   
7 J6 q' @, I: [# X4 C( w    count=count+1;
$ ^2 a4 s8 L6 J0 d, j& M6 a3 [   
$ i: ?& t$ k9 _0 tend
% f9 z6 j! S6 [( w( etree_border=tree_node;
-----------------------------
. i1 J! u8 z/ \# D5 B' A8 Zfunction flag=node_judge(tree_node,index_x,index_y)
flag=0;
n=length(tree_node);
flag_x=0;
; v- e5 V, ~# ]. s( i' c4 sflag_y=0;
( V# J6 s' g' Q: L! s1 T2 efor i= 1:n
    if tree_node(i)==index_x
        flag_x=1;
& F, r1 e) i; J9 r* U  [2 v9 g6 V    end
& O0 H& W1 d2 u& I, R5 }    if tree_node(i)==index_y
/ S) K  C$ I6 L. p: k$ ~/ e        flag_y=1;
& L5 H) Q3 ^1 h7 i    end
end
1 [& n1 H% [% dif flag_x==1&&flag_y==1
2 y3 o$ g0 `" H$ \, y) A# \3 E    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
/ w8 J6 Y. D) B+ A3 x

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

- [. Z& b* E3 v找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...