最小数prim算法

水木年华zzu

求最小树的prim算法
! `, i: b. x* E+ i* W. S: V说明：tree_border 向量中相邻的两个元素为边的顶点，例如，第1个元素和2个元素为一条边的两个顶点，第3个元素和第4个元素为一条边的两个顶点，依次内推，将个跳边连起来就形成了最小生成树。
function [tree_martix,tree_border]=min_tree(a)
n= size(a,1);
a_copy=a;
5 f( O2 y% q2 B9 F* S! ~for i= 1:n
    for j=i:n
2 W- O' s9 h% v1 Q7 k" F( O, [- G  H        a_copy(i,j)=inf;
3 I$ P& Y, ]2 i* {8 O    end
: S* K$ `# F, F4 send
3 c' B- l( {2 y1 J: qtree_martix=zeros(n,n);
count=0;

tree_node=zeros(2*n,1);
8 V; P# A) Z# D$ X3 [, Si=1;
! _; y0 U9 F9 z  ?! }, w  J! ~2 |8 Twhile count<=n-2
/ D$ X; S4 F3 \; I7 \! G  u    b=min(min(a_copy));
( E0 {5 d2 \% G4 ~& J( \8 N" l    [index_x,index_y]=find(a_copy==b);
- v+ v) p' @  Z! i     flag=node_judge(tree_node,index_x,index_y);
    if flag==1
     a_copy(index_x,index_y)=inf;
     a_copy(index_y,index_x)=inf;
5 p- E% X3 ?9 z' l; [        continue;
0 o8 P+ C0 J: }. E# i4 D5 M    end
    tree_node(i)=min(index_x);
4 H( e% z* ~: J6 R! z( i) m    tree_node(i+1)=min(index_y);
    i=i+2;
/ u4 S# l6 N- _( F( E0 k' H    %a_copy(index_x,index_y)=inf;
' c4 |( h. Z; g% ?+ g+ W% ]6 x    %a_copy(index_y,index_x)=inf;
4 ?$ ]% |/ j* U7 k2 y! m, P# K    tree_martix(index_x,index_y)=a_copy(index_x,index_y);
; t9 s* b% _9 {# b- W    a_copy(index_x,index_y)=inf;
4 v* [6 {. ]% |/ |# x5 [& E- k8 B" @    a_copy(index_y,index_x)=inf;
4 V) I( n9 s7 r5 P  c   
    count=count+1;
   
# x+ i. W$ c0 C: h1 Fend
9 L! N$ s; a0 [7 a& gtree_border=tree_node;
-----------------------------
function flag=node_judge(tree_node,index_x,index_y)
6 r! [$ U! ?5 p; Q4 e9 t$ F1 S  n" Q5 Mflag=0;
8 q6 d; Z6 m* `; sn=length(tree_node);
flag_x=0;
flag_y=0;
7 t5 L: |7 z; k2 jfor i= 1:n
    if tree_node(i)==index_x
3 U6 {; O/ R$ r4 ?        flag_x=1;
2 z8 d- o+ X3 |  y  Q- C5 u    end
: F( |8 b6 C8 m& o5 U( E    if tree_node(i)==index_y
        flag_y=1;
% d- W5 ?* j) I  y$ v0 y9 M! I    end
end
if flag_x==1&&flag_y==1
( N  L1 E8 @/ p* K    flag=1;
$ f& R# v, Z# E0 f7 z, n6 B  cend

大笨象

谢谢分享程序～

zhangkay

谢谢分享程序～
5 c# s2 D5 b/ \! T3 B# I

qluther

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

qluther

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

gssrb

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

效忠w手掌

谢谢分享程序的人，

水木年华zzu

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

: k, `  R  {( S$ \. J6 F找几个矩阵验算下就行了

小叮当1016

谢谢分享程序～

朱鑫鑫

...