最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
: ?1 H/ O* N; C- la_copy=a;
for i= 1:n
7 j% X" i9 A: J    for j=i:n
        a_copy(i,j)=inf;
0 O# i  ]( d3 q, i! q$ H, W3 l    end
end
tree_martix=zeros(n,n);
8 j' |8 F1 ~3 l7 b) ycount=0;

tree_node=zeros(2*n,1);
( ?# }  \  Q% E4 B% ji=1;
while count<=n-2
$ e9 R/ K6 o' r' n    b=min(min(a_copy));
$ f0 s  ]- {* t; i0 X5 s% ~& i% a    [index_x,index_y]=find(a_copy==b);
     flag=node_judge(tree_node,index_x,index_y);
5 y% }* }. ]- L+ Z# ]    if flag==1
     a_copy(index_x,index_y)=inf;
8 \1 y5 r% c& a, K9 v% l$ `/ S  _( V     a_copy(index_y,index_x)=inf;
        continue;
" m9 h9 g5 P- u- b    end
1 {# [6 v; S, k: Q& y    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
    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);
    a_copy(index_x,index_y)=inf;
    a_copy(index_y,index_x)=inf;
   
3 X! h' r- f9 G  a. p    count=count+1;
* `+ m  K$ s- \5 I- i# B: M# t   
end
tree_border=tree_node;
-----------------------------
& t- ~* S0 y( Ifunction flag=node_judge(tree_node,index_x,index_y)
4 O4 l! C8 F$ `) X# xflag=0;
n=length(tree_node);
flag_x=0;
+ x# w# U' O2 A" z9 I% G& C5 {! Sflag_y=0;
2 F( {$ W6 u9 s4 I; b8 H6 Tfor i= 1:n
    if tree_node(i)==index_x
  H1 `* Z) [( B' V        flag_x=1;
  P% a6 A# l. [3 O    end
. c' w' O2 b6 h9 J9 ^: U* y% R    if tree_node(i)==index_y
        flag_y=1;
    end
" A# w$ b' f  D+ nend
- R6 z( O- o; w5 S: Oif flag_x==1&&flag_y==1
& {7 s& D4 m7 f9 ^& j    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
/ k5 c8 H8 b. l! s0 t

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

; o$ P& w! O8 |$ d$ [; G7 L: s# R/ `. g找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...