如何编写对树中节点的后代进行计数的迭代DFS

Question

我在转换以下代码时遇到问题：

void dfs(int i = 1) {
  static int preorder = 0;
  d[i].first = ++preorder;
  d[i].second = 1;
  for (list<int>::iterator it = tree[i].begin(); it != tree[i].end(); ++it) {
    dfs(*it);
    d[i].second += d[*it].second;
  }
}

转换为迭代。正如您所看到的，它可以找到每个节点的预购号以及它有多少子节点。由于内存限制（数据大小最大为10^6），我不得不这么做。

提前谢谢。

Answer 1

DFS是一种递归算法。

如果您试图避免耗尽堆栈空间，可以使用显式堆栈（将隐式调用堆栈转换为显式节点堆栈）。但我认为你无法摆脱这是一个递归算法的事实。

即使您使用的是显式堆栈，您仍然可能耗尽内存。这取决于系统中的内存量和树的形状。但在大多数情况下，它至少可以避免严重的崩溃（当堆内存用完时可以检测到）。

Answer 2

我终于弄明白了。它可能不那么快，但它足够快，可以在不消耗太多记忆的情况下通过测试。我需要从孩子到他父亲的指针（只有8MB的称为ojciec的数组），并检测节点是第一次访问（下降）还是没有访问（上升）。这是我的代码：

void dfs()
{
  int preorder = 0;
  int i;
  stack<int, list<int> > stos;
  stos.push(1);
  while(!stos.empty()) {
    i = stos.top();
    if (order[i] == 0) { // node is first time visited
      order[i] = ++preorder; // set default values
      size[i]  = 1;
    }
    if (dynastia[i] != NULL) // can go left...
      stos.push( pop( &dynastia[i] ) ); // so take first child, remove it and release memory
    else {
      stos.pop();
      size[ojciec[i]] += size[i]; // adding total number of descendants to father
    }
  }
}