// Traversal routines --- parameter is the start city

// Each of the following uses a private member function
   public void depthRecur ( String start )  // Recursive depth-first
   // Entry point
   {//Decode start subscript
      int  first = findCity(start);

      if (first < 0)
      {  System.err.println ("Unknown starting point " + start
              + " --- abort!");
         return;
      }

      clearFlags();
      depthRecur ( -1, first );

   // Take care of possible unconnected components
      for ( first = 0; first < m_Size; first++ )
         if (m_City[first].getFlag() == UNVISITED)
            depthRecur ( -1, first );
   }

   protected void depthRecur ( int src, int dst )
   // Implementation code
   {  CPair edge = new CPair(src, dst);
      CEdge current = m_City[dst].list();

      m_Sequence[m_NextEdge++] = edge;
   // Save position in the list
      m_City[dst].setFlag(m_NextEdge);

      src = dst;
      for ( ; current != null; current = current.next() )
      {  int flag;

         dst = current.city();
         flag = m_City[dst].getFlag();
         if (flag == UNVISITED )
            depthRecur (src, dst);
      }
   }

   public void depth1st   ( String start )  // Iterative depth-first
   // Entry point
   {//Decode start subscript
      int first = findCity(start);

      if (first < 0)
      {  System.err.println ("Unknown starting point " + start
              + " --- abort!");
         return;
      }

      clearFlags();
      depth1st ( first );

   // Take care of possible unconnected components
      for ( first = 0; first < m_Size; first++ )
         if (m_City[first].getFlag()==UNVISITED)
            depth1st ( first );
   }

   void depth1st ( int first )
   // Implementation code
   {  CPair edge = new CPair(0,0);
      Deque work = new Deque() ;
      CEdge current;

      edge.set(-1, first);      // Pseudo-edge for entry point
      work.push(edge);

   // As long as work remains . . .
      while ( ! work.empty() )
      {  edge = work.remove();
         int src = edge.get1();
         int dst = edge.get2();
         if ( m_City[dst].getFlag() != UNVISITED )
            continue;

      // CRITICAL:  new edge object, NOT just the reference!
         m_Sequence[m_NextEdge++] = new CPair(edge);
      // Save position in the list
         m_City[dst].setFlag(m_NextEdge);

         current = m_City[dst].list();
         src = dst;
         for ( ; current != null; current = current.next() )
         {  int flag;

            dst = current.city();
            flag = m_City[dst].getFlag();
            edge.set(src, dst);

            if (flag == UNVISITED )
            {
               work.push(edge);
            }
         }
      }
   }

   public void breadth1st ( String start )  // Breadth-first
   // Entry point
   {//Decode start subscript
      int first = findCity(start);

      if (first < 0)
      {  System.err.println ("Unknown starting point " + start
              + " --- abort!");
         return;
      }

      clearFlags();
      breadth1st ( first );

   // Take care of possible unconnected components
      for ( first = 0; first < m_Size; first++ )
         if (m_City[first].getFlag()==UNVISITED)
            breadth1st ( first );
   }

   void breadth1st ( int first )
   // Implementation code
   {  CPair edge = new CPair(0,0);
      Deque work = new Deque() ;
      CEdge current;

      edge.set(-1, first);      // Pseudo-edge for entry point
      work.enqueue(edge);

   // As long as work remains . . .
      while ( ! work.empty() )
      {  edge = work.remove();
         int src = edge.get1();
         int dst = edge.get2();
         if ( m_City[dst].getFlag() != UNVISITED )
            continue;

      // CRITICAL:  new edge object, NOT just the reference!
         m_Sequence[m_NextEdge++] = new CPair(edge);
      // Save position in the list
         m_City[dst].setFlag(m_NextEdge);

         current = m_City[dst].list();
         src = dst;
         for ( ; current != null; current = current.next() )
         {  int flag;

            dst = current.city();
            flag = m_City[dst].getFlag();
            edge.set(src, dst);

            if (flag == UNVISITED )
            {
                  work.enqueue(edge);
               }
            }
      }
   }