Как написать итеративную 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

Наконец-то я понял это.Это может быть не так быстро, но достаточно быстро, чтобы пройти тесты, не съедая слишком много памяти.Мне были нужны указатели от ребенка до его отца (всего 8 МБ массива, называемого 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
    }
  }
}

Answer 2

DFS - рекурсивный алгоритм.

Если вы пытаетесь избежать исчерпания пространства стека, вы можете использовать явный стек (преобразовать неявный стек вызовов в явный стек узлов).Но я не думаю, что вы можете избежать того факта, что это рекурсивный алгоритм.

Даже если вы используете явный стек, у вас все равно может быть недостаточно памяти.Это зависит от объема памяти в вашей системе и формы дерева.Но в большинстве случаев это, по крайней мере, позволит избежать неприятного сбоя (вы можете обнаружить, когда у вас заканчивается куча памяти).