最小数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
+ K2 a3 I; A: m  j) q0 k$ M5 B! @    for j=i:n
  \; C7 Z) T; q; d% n5 f: w  U        a_copy(i,j)=inf;
2 u' ^. I3 I  l  E$ L( v, `+ G, d    end
) M5 \0 z. Q/ ^- qend
, t+ Z% \9 O% g5 ^' vtree_martix=zeros(n,n);
count=0;
8 b( y0 n6 r7 s& i- u8 C
tree_node=zeros(2*n,1);
i=1;
) w, k6 q" @5 P2 c! a. \0 mwhile count<=n-2
    b=min(min(a_copy));
% `7 L. a' d5 c7 v1 Y    [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;
& @' |' y! ]- \1 _1 Y- W4 ~     a_copy(index_y,index_x)=inf;
        continue;
    end
    tree_node(i)=min(index_x);
+ L# i  ?: e  w+ ]1 K    tree_node(i+1)=min(index_y);
( ^- i- u  T/ }8 j& U    i=i+2;
. R) q0 N+ D: v2 q# I! l    %a_copy(index_x,index_y)=inf;
) }# G9 Q3 p2 D* B! _6 L    %a_copy(index_y,index_x)=inf;
+ r, m8 w; J0 q3 q# {* P3 r    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
( F; P( v$ [+ R    a_copy(index_x,index_y)=inf;
) P  z! j0 [& b  p8 j    a_copy(index_y,index_x)=inf;
   
    count=count+1;
   
end
tree_border=tree_node;
7 q4 D' }: d2 e% i  G; ~  N-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
+ @7 Z: a5 I3 Z. j* Z. X" H* T& Hflag=0;
* a% g) ~+ B2 t, k) y, Bn=length(tree_node);
flag_x=0;
flag_y=0;
! |3 d$ d7 u8 N! g/ L- T0 H* Zfor i= 1:n
9 F: \1 ]: ^3 X1 x    if tree_node(i)==index_x
        flag_x=1;
    end
    if tree_node(i)==index_y
% J3 W0 D% C0 J6 M- [3 b        flag_y=1;
    end
2 ?# k6 m. h- A8 x; z  w  uend
if flag_x==1&&flag_y==1
, V  G: }1 T2 R  V0 K& y7 P    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
# }1 {! x* k* p- z( d0 D/ s

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

qluther 发表于 2010-8-15 12:41
- I$ e" q$ W6 b  d  V2 `; O+ H% E程序好像有问题吧：只是把权矩阵中的最小值一次加入到tree_border中，没有管是否已经联通所有的点，或者是否 ...

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...