1

我在打开此代码时遇到问题：

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），我必须这样做。

提前致谢。

4

2 回答 2

0

DFS 是一种递归算法。

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

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

于 2012-02-19T22:04:56.447 回答
0

最后我想通了。它可能不是那么快，但它足够快，可以在不消耗太多内存的情况下通过测试。我需要孩子指向他父亲的指针（只有 8 MB 数组，称为 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
    }
  }
}
于 2012-02-20T08:49:57.107 回答