c-----------------------------------------------------------
c Chapter 30: Tree of Minimal Length(p283)
c-----------------------------------------------------------
c   Name of subroutine: MINSPT
c
c   Algorithm:Find spanning tree of minimal length.
c
c   input:  n=5  
c   complier: f77 minspt_2.f
c-----------------------------------------------------------

      parameter(n=5,ndim=2)
      real dist(n,n)
      integer tree(n)
      do 10 i=1,n
      read(*,20),(dist(i,j),j=1,n)
20    format(5(f6.1))
10    continue
      call minspt(n,ndim,dist,tree)
      write(*,50) (tree(i),i=1,n-1)
50    format(5(i2))
      stop
      end

c-----Subroutine begins here--------------------------------
      subroutine minspt(n,ndim,dist,tree)
      real dist(n,n)
      integer tree(n)
      nm1=n-1
20    do 21  i=1,nm1
21    tree(i)=-n
      tree(n)=0
25    do 51 l=1,nm1
      dmin=1.e50
40    do 41 i=1,nm1
      it=tree(i)
      if(it.gt.0) go to 41
      d=dist(-it,i)
      if(d.ge.dmin) go to 41
      dmin=d
      imin=i
41    continue
      tree(imin)=-tree(imin)
50    do 51 i=1,nm1
      it=tree(i)
      if(it.gt.0) go to 51
      if(dist(i,imin).lt.dist(i,-it)) tree(i)=-imin
51    continue
      return
      end