This pseudocode is a modified version of a Fortran subroutine originally
published by V.K.M. Whitney in Communications of the Association for
Computing Machinery (ACM) in 1972, Algorithm 422 minimal spanning tree [H],
15(4), 273-274.  The Fortran code has been recently digitized and is
available as file 422 from the ACM at http://www.acm.org/calgo/contents/.
Because the algorithm in this pseudocode has been modified, the ACM is not
responsible for its accuracy. This pseudocode may contain material
copyrighted by ACM. Please view the ACM copyright agreement at:
http://www.acm.org/pubs/copyright_policy/softwareCRnotice.html



PSEUDOCODE FOR THE MODIFIED MINIMAL SPANNING TREE ALGORITHM
-----------------------------------------------------------
(all variables are 32-bit integers unless noted as "float")


G	2D input matrix (float) representing the graph.
n       Number of nodes in the graph.

MST	2D output matrix which stores the two node indices of each edge in
	the minimal spanning tree (MST).
smst	Sum of all the edge weights in the MST (float).
nmst	Number of edges in the MST.

nnit	Number of nodes not yet in MST.
new	Index for the newest node added to the MST.
NIT	Array holding indices for those nodes not yet in the MST.
INMST	Array holding closest node in MST to each node in NIT.
DM2N	Array holding edge weight from IMST(i) to NIT(i) (float).
sdist	Shortest edge weight in array DM2C (float).
inear	Index for the node outside the MST that is nearest to the MST.

Initialize smst to 0.0.
Initialize nnit to n - 1  <= initial number of nodes not yet in MST is n-1.
Initialize new to n       <= last node in G will be the first node in MST.
Initialize nmst to 0


do for each i = 1, nnit
  NIT(i) = i           <= indices for all nodes not yet in the MST.
  DM2N(i) = G(i)(new)  <= edge weights from new to all nodes not in MST.
  INMST(i) = new       <= since new is the only node in MST, it is closest.

while nnit is greater than zero do the following:
  do for each i = 1, nnit
    if  G(NIT(i))(new) < DM2N(i)  then   <= if new node is closer to NIT(i) 
      DM2N(i) = G(NIT(i))(new)              update arrays DM2N and INMST.
      INMST(i) = new 

  sdist = DM2N( 1)                       <= assume first edge is smallest
  do for each i = 1, nnit
    if    DM2N(i) < sdist     then       <= find the node outside that is
      inear = i                             closest to partial MST
      sdist = DM2N(i)

  nmst = nmst + 1
  MST(nmst)(1) = NIT(inear)     <= add the new node to the MST
  MST(nmst)(2) = INMST(inear)
  smst = smst + sdist
  new = NIT(inear)

  DM2N(inear) = DM2N(nnit)   <= delete the new node from DM2N, NIT, and
  NIT(inear) = NIT(nnit)        INMST by replacing it with the last
  INMST(inear) = INMST(nnit)    node in NIT which is nnit.
  nnit = nnit - 1            <= decrease the number of nodes not in MST.


when nnit = 0 then all nodes are in the MST.  Return to the calling module.