c++ - 树的 DFS 递归，需要有关已访问问题的帮助

Question

我在尝试导航包含循环的树时遇到问题。我的代码进入无限循环和核心转储。我的问题是我的代码没有将节点设置为在实际访问它们之后访问它们，所以它只会永远循环。非常感谢任何帮助。

#include "GraphCode.h"
//#define EBUG

/******************************************************************************
static const string TAG = "GraphCode: ";

/******************************************************************************
 * Constructor
**/
GraphCode::GraphCode()
{
}

/******************************************************************************
 * Destructor
**/
GraphCode::~GraphCode()
{
}

/******************************************************************************
 * Accessors and Mutators
**/

/******************************************************************************
 * General functions.
**/

/******************************************************************************
 * Function 'createGraph'.
 * We read data from the input stream and create a graph.
 *
 * Parameter:
**/
void GraphCode::createGraph(Scanner& inStream)
{
  int nodeCount = -10;
  double connectivity = -3.5;

  MyRandom myRandom;
#ifdef EBUG
#endif
  cout << TAG << "enter createGraph\n"; 

  if (inStream.hasNext())
  {
    nodeCount = inStream.nextInt();
    connectivity = inStream.nextDouble();
    cout << TAG << "Create a graph of " << nodeCount
                << " nodes and " << connectivity << " percent connections"
                << endl;
  }
  else
  {
    cout << TAG << "NO DATA\n"; 
  }

  // first we create the vector of empty nodes
  for (int fromNum = 0; fromNum < nodeCount; ++fromNum)
  {
    Node node = Node(fromNum);
    this->theGraph.push_back(node);
  }

  // now we have a vector so we know we can subscript
  for (int fromNum = 0; fromNum < nodeCount; ++fromNum)
  {
    Node node = this->theGraph.at(fromNum);
    for (int toNum = 0; toNum < nodeCount; ++toNum)
    {
      if (fromNum == toNum) continue;
      double r = myRandom.randomUniformDouble(0.0, 1.0);
      if (r <= connectivity)
      {
        node.addChildSub(toNum);
      }
    }
    this->theGraph[fromNum] = node;
  }

#ifdef EBUG
#endif
  cout << TAG << "leave createGraph " << nodeCount << " " << connectivity << endl; 
} // void GraphCode::createGraph(Scanner& inStream)

/******************************************************************************
 * Function 'descendFrom'.
**/
void GraphCode::descendFrom(ofstream& outStream, string blanks, Node& parentNode)
{
#ifdef EBUG
  cout << blanks << TAG << "enter descendFrom\n" << this->toStringPath(blanks) << endl;
#endif

  vector<int> listOfChildren = parentNode.getChildSubs();
  vector<int>::const_iterator iter;
  if (parentNode.hasBeenVisited() == false) 
  {
    path.push_back(Utils::Format(parentNode.getNodeNumber()));
    parentNode.setVisited(true);
    if (listOfChildren.empty())
    {
      outStream << "Path""\n" << toStringPath(blanks) << endl;
      path.pop_back();
    }

    else
    {
      for (iter = listOfChildren.begin(); iter != listOfChildren.end(); iter++)
      {
        Node& n = theGraph.at(*iter);
        descendFrom(outStream, blanks, n);
      }
     path.pop_back();
    }
  }
 #ifdef EBUG
  cout << blanks << TAG << "leave descendFrom\n"; 
#endif

} // GraphCode::descendFrom()

/******************************************************************************
 * Function 'doSearch'.
**/
void GraphCode::doSearch(ofstream& outStream)
{
#ifdef EBUG
  cout << TAG << "enter doSearch\n"; 
#endif

Node& node = theGraph.at(0);
string blanks = "     ";
descendFrom(outStream, blanks, node);


#ifdef EBUG
  cout << TAG << "leave doSearch\n"; 
#endif

} // void GraphCode::doSearch()

/******************************************************************************
 * Function 'readGraph'.
**/
void GraphCode::readGraph(Scanner& inStream)
{
  ScanLine scanLine;

#ifdef EBUG
  cout << TAG << "enter readGraph\n"; 
#endif

  int firstNode, lastNode;
  firstNode = inStream.nextInt();
  lastNode = inStream.nextInt();
  assert ( 0 == firstNode);
  for(int i = 0; i <= lastNode; ++i)
  {
    Node node = Node(i);
    this->theGraph.push_back(node);
  }

  while (inStream.hasNext())
  {
    string theLine = inStream.nextLine();

    scanLine.openString(theLine);
    int parentNodeNum = scanLine.nextInt();
    Node node = this->theGraph.at(parentNodeNum);
    while( scanLine.hasNext())
    {
      int theChild = scanLine.nextInt();

      node.addChildSub(theChild);
    }
    this->theGraph.at(parentNodeNum) = node;
  }

#ifdef EBUG
  cout << TAG << "leave readGraph " << endl;
#endif
} // void GraphCode::readGraph(Scanner& inStream)

/******************************************************************************
 * Function 'toString'.
**/
string GraphCode::toString()
{
  Node node;
  string s = "     ";
#ifdef EBUG
  cout << TAG << "enter toString\n"; 
#endif
  vector<Node>::const_iterator iter;
  for (iter = theGraph.begin(); iter != theGraph.end(); iter++)
  {
    node = *iter;
    s += "Node:  (" + node.toString() + ")" + "\n";
  }
#ifdef EBUG
  cout << TAG << "leave toString\n"; 
#endif
  return s;
} // string GraphCode::toString()

/******************************************************************************
 * Function 'toStringChildren'.
**/
string GraphCode::toStringChildren(string blanks, const vector<int>& children)
{
  string s = "";
#ifdef EBUG
  cout << TAG << "enter toStringChildren\n"; 
#endif
  Node node;
  vector<int>::const_iterator iter;
  for (iter = children.begin(); iter != children.end(); ++iter)
  { 
    s += Utils::Format((*iter), 6);
  }
#ifdef EBUG
  cout << TAG << "leave toStringChildren\n"; 
#endif
  return s;
} // string GraphCode::toStringChildren()

/******************************************************************************
 * Function 'toStringPath'.
**/
string GraphCode::toStringPath(string blanks)
{
  string s = "     ";
#ifdef EBUG
  cout << TAG << "enter toStringPath\n"; 
#endif
  Node node;
  for (int index = 0; index < this->path.size(); ++index)
  {
    s += this->path.at(index) + "\n" + blanks;
  } 
  s += "LEAF\n";
#ifdef EBUG
  cout << TAG << "leave toStringPath\n"; 
#endif
  return s;
} // string GraphCode::toStringPath()

//预期输出:

//PATH TO LEAF 
                           // PATH (   0:  T    1   2   6   9 XXX)
                            //From (   1:  T  XXX)
                           // LEAF

//PATH TO LEAF 
                              //PATH (   0:  T    1   2   6   9 XXX)
                              //From (   2:  T    3   4   5 XXX)
                              //From (   3:  T  XXX)
                              //LEAF

//my output:  
//Path
   //  0
   //  1
   //  LEAF

//Path
    // 0
    // 2
    // 3
    // LEAF

我已经正确地打印出路径，但我无法获得“T”(基本上是调用 parentNode.toString())和子节点打印在与路径相同的行上

Answer 1

void Node::setVisited(bool what)
{
  what = visited; 
}

那个赋值是倒着的。你的意思是

visited = what;