Как написать итерационный 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 - это рекурсивный алгоритм.

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

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