最小数prim算法

水木年华zzu

求最小树的prim算法
说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
8 w4 Z% w$ L* H  I, j$ w, ea_copy=a;
0 ]) E1 S; j) g" ^* afor i= 1:n
' v/ ?) H" q5 N9 \* k- h; f! ]    for j=i:n
        a_copy(i,j)=inf;
    end
8 Z, g( N; f4 p$ j7 ]end
tree_martix=zeros(n,n);
count=0;

tree_node=zeros(2*n,1);
i=1;
+ g- `- A" w; Z$ `while count<=n-2
    b=min(min(a_copy));
& k  P7 v3 t6 }% P; t- F9 `    [index_x,index_y]=find(a_copy==b);
: @& ~  W% \, E# A7 |( a# ~: A( x/ \     flag=node_judge(tree_node,index_x,index_y);
: H6 ]% K. j$ c9 S    if flag==1
' G( C4 A" M* w$ ?0 `2 E9 Y" a     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
        continue;
% b8 i1 D4 J! ?( S5 N    end
    tree_node(i)=min(index_x);
    tree_node(i+1)=min(index_y);
    i=i+2;
    %a_copy(index_x,index_y)=inf;
" u# o, s! I# @. T& K, q    %a_copy(index_y,index_x)=inf;
- j4 w3 H& v& v1 K# {# p; I    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;
: H: D9 A! L& y6 @4 e0 I, r* V   
    count=count+1;
   
end
tree_border=tree_node;
-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
flag=0;
4 n# v1 F0 U$ ?, Jn=length(tree_node);
% w/ v& J6 I# e% r# P( cflag_x=0;
flag_y=0;
for i= 1:n
    if tree_node(i)==index_x
        flag_x=1;
  A4 D( Z/ D# Q, Q% m! s    end
    if tree_node(i)==index_y
        flag_y=1;
, ^! j3 {8 A1 z) L% q' C. r    end
- _5 B0 ?) T0 zend
1 i6 o8 G& H5 S8 C. E/ Tif flag_x==1&&flag_y==1
    flag=1;
1 L3 n0 _' v6 r2 ]) Kend

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

qluther 发表于 2010-8-15 12:41
( Q7 L7 f4 P% W& H2 I5 q5 l+ z, ~: a程序好像有问题吧：只是把权矩阵中的最小值一次加入到tree_border中，没有管是否已经联通所有的点，或者是否 ...

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...