最小数prim算法

水木年华zzu

求最小树的prim算法
  k6 K# `3 z" W/ W说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
! t% x; ?, p% P' z9 ma_copy=a;
8 f+ ^1 ]8 d2 U& q8 hfor i= 1:n
    for j=i:n
        a_copy(i,j)=inf;
    end
end
tree_martix=zeros(n,n);
count=0;

tree_node=zeros(2*n,1);
: s' A3 y9 K) r1 vi=1;
while count<=n-2
- n( o, R% J# y0 T- P: z$ O9 y    b=min(min(a_copy));
    [index_x,index_y]=find(a_copy==b);
' L+ f5 O; M+ e; l7 G     flag=node_judge(tree_node,index_x,index_y);
: j4 \' Z4 h/ d% D  a6 P0 y1 i: S    if flag==1
0 D1 ~+ j* X- l) S6 R     a_copy(index_x,index_y)=inf;
, W5 j! f% S, ]# S& X7 Z     a_copy(index_y,index_x)=inf;
2 f& t. h6 r- x        continue;
2 a& x, m- M& c( Y    end
    tree_node(i)=min(index_x);
7 j7 U$ p+ U# W$ G4 G; ?' I    tree_node(i+1)=min(index_y);
    i=i+2;
    %a_copy(index_x,index_y)=inf;
, M1 [2 A) V/ ?! @    %a_copy(index_y,index_x)=inf;
2 p( ?+ ]2 o( c# I9 O    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
    a_copy(index_x,index_y)=inf;
- c  q, L0 f: @! t    a_copy(index_y,index_x)=inf;
   
( [- F8 m2 ^, G: a& K    count=count+1;
   
; {2 z3 N4 k# v- Vend
tree_border=tree_node;
- Q$ Z% W; d# \  @-----------------------------
0 X: Y6 I8 O5 Y- H/ b0 Qfunction flag=node_judge(tree_node,index_x,index_y)
flag=0;
n=length(tree_node);
flag_x=0;
flag_y=0;
# u% r$ g/ R2 i5 H- o4 r: Ffor i= 1:n
    if tree_node(i)==index_x
        flag_x=1;
3 g# h& ^5 {0 P+ X8 r6 Z) C    end
    if tree_node(i)==index_y
3 V, t  T9 A1 ?( ^: `3 |* D: B        flag_y=1;
2 B: a! v1 W3 j' a- X    end
end
if flag_x==1&&flag_y==1
    flag=1;
. `0 C4 ^# P2 b/ l" W$ S& ^end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...