如何编写迭代 DFS 来计算树中节点的后代

发布于 2025-01-07 06:37:11 字数 365 浏览 3 评论 0原文

我在将此代码转换

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

提前致谢。

原文

I have problem with turning this code:

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;
  }
}

into iterative one. As you can see, it finds preorder number of each node and how many descendants it has.
I have to do it, because of memory limitation (data size is up to 10^6).

Thanks in advance.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

若能看破又如何 2025-01-14 06:37:11

DFS是一种递归算法。

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

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

回复收藏 0 原文

木森分化 2025-01-14 06:37:11

终于我弄清楚了。它可能不是那么快，但足够快地通过测试而不会消耗太多内存。我需要从孩子到他父亲的指针（只有 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
    }
  }
}

Finally I've figure it out. It may be not so fast but it is fast enough to get passed through tests without eating too much memory. I needed pointers from child to his father (just 8 MB array called ojciec) and detect if node is first time visited (going down) or not (going up).
Here is my code:

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
    }
  }
}

回复收藏 0 原文

~没有更多了~