function [ class, itree, jtree ] = graph_dist_min_span_tree2 ( nnode, dist )

%*****************************************************************************80
%
%% graph_dist_min_span_tree2() computes a spanning tree of minimal length.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    06 November 2024
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer NNODE, the number of nodes.
%
%    real DIST(NNODE,NNODE).  DIST(I,J) = distance from node I to node J.
%
%  Output:
%
%    integer CLASS(NNODE), lists the nodes in the order in
%    which they joined the tree.
%
%    integer ITREE(NNODE-1), JTREE(NNODE-1), the pairs of
%    nodes that form the edges of the tree.
%
  class = zeros ( nnode, 1 );
  itree = zeros ( nnode - 1, 1 );
  jtree = zeros ( nnode - 1 , 1 );
  
  if ( nnode <= 1 )
    return
  end
%
%  All the nodes start out in the negative class.
%
  npos = 0;
  for i = 1 : nnode
    class(i) = i;
  end
%
%  Find the shortest edge (I,J).
%
  unset = true;
  dmin = 0.0;

  for i = 1 : nnode
    for j = i + 1 : nnode

      if ( unset )
        smaller = true;
      elseif ( dist(i,j) < dmin )
        smaller = true;
      else
        smaller = false;
      end

      if ( smaller )
        imin = i;
        jmin = j;
        dmin = dist(i,j);
        unset = false;
      end

    end
  end
%
%  Carry nodes IMIN and JMIN into the positive class.
%
  npos = npos + 1;
  temp = class(npos);
  class(npos) = class(imin);
  class(imin) = temp;

  npos = npos + 1;
  temp = class(npos);
  class(npos) = class(jmin);
  class(jmin) = temp;

  itree(1) = imin;
  jtree(1) = jmin;
%
%  Now, repeatedly, find the shortest edge connecting a negative
%  and positive node.  Move the negative node to the positive class and
%  repeat.
%
  for k = 2 : nnode - 1

    unset = true;
    dmin = 0.0;
    imin = - 99;
    jmin = - 99;

    for ii = 1 : npos

      i = class(ii);

      for jj = npos + 1 : nnode

        j = class(jj);

        if ( unset )
          smaller = true;
        elseif ( dist(i,j) < dmin )
          smaller = true;
        else
          smaller = false;
        end

        if ( smaller )
          imin = i;
          jmin = j;
          jjmin = jj;
          dmin = dist(i,j);
          unset = false;
        end

      end

    end

    npos = npos + 1;
    temp = class(npos);
    class(npos) = class(jjmin);
    class(jjmin) = temp;

    itree(k) = imin;
    jtree(k) = jmin;

  end

  return
end
