Как написать итеративную DFS, которая подсчитывает потомки узла в дереве

У меня проблема с включением этого кода:

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

в итеративный. Как вы можете видеть, он находит номер предварительного заказа каждого узла и количество его потомков. Я должен сделать это из-за ограничения памяти (размер данных до 10 ^ 6).

Заранее спасибо.

2 ответа

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


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

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

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

licensed under cc by-sa 3.0 with attribution.