最小数prim算法

水木年华zzu

求最小树的prim算法
- U  _) ~2 a6 {说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
/ B2 x6 i5 d( y5 O3 Zn= size(a,1);
; H2 i3 q0 N- ea_copy=a;
for i= 1:n
, N/ U/ l! R; y5 e* [    for j=i:n
        a_copy(i,j)=inf;
    end
( F9 A3 ?# _7 m* L$ q8 Uend
tree_martix=zeros(n,n);
count=0;
) e: H  L, Z$ L* S$ ^
' T; S- D8 h* x8 `) otree_node=zeros(2*n,1);
i=1;
while count<=n-2
; Z3 w* S9 ^, p7 y4 B    b=min(min(a_copy));
# j. n! M3 q: A* m: _    [index_x,index_y]=find(a_copy==b);
% @. n) ]& B/ p' C) x9 S     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
% D' ~. Z5 w9 e1 T$ J' N     a_copy(index_x,index_y)=inf;
( z; ?' S% _2 k; d     a_copy(index_y,index_x)=inf;
        continue;
    end
& G& n  T! Z+ N: S& E    tree_node(i)=min(index_x);
* J* B, z! W8 {4 x2 U* }2 [8 d- D    tree_node(i+1)=min(index_y);
    i=i+2;
, K1 K) a/ q7 O9 ~8 m    %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;
5 @: q. A: D' N7 Z4 c- T" k% [6 H& x    a_copy(index_y,index_x)=inf;
   
/ ?  e! W9 j) ^" r$ _( i$ t    count=count+1;
   
' T6 `/ z3 R5 C: ^) w# oend
tree_border=tree_node;
7 C2 n& U6 e" }8 F) y. g0 @-----------------------------
" h$ `+ L7 T. E" p- t$ tfunction flag=node_judge(tree_node,index_x,index_y)
5 P9 z) H4 Q$ q  Nflag=0;
1 H% |% \2 J. ^n=length(tree_node);
. j- M  O7 \& K1 i" X# S1 Mflag_x=0;
flag_y=0;
for i= 1:n
    if tree_node(i)==index_x
4 Q! u# |- k; H7 X        flag_x=1;
8 G( B5 i9 T" u. w9 Q% H    end
    if tree_node(i)==index_y
! K3 o: n7 Z( D8 z5 D        flag_y=1;
    end
end
! T* _0 ]- W# Dif flag_x==1&&flag_y==1
0 ]8 T2 ~9 |, F5 A( O    flag=1;
end

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
  Z* r2 U7 U0 c$ d

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

% ]: P( ?% g( E; d找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...