Топологическая сортировка с использованием Итерация вместо рекурсии

Question

я изначально имел рекурсивное решение для топологической сортировки:

void dfs(int v, bool visited[], node* adjList[], std::stack<int> &myStack) { 
    visited[v] = true; 
    node* curr = adjList[v]; 

    while (curr != NULL) { 
     if(!visited[curr->val]) { 
      dfs(curr->val, visited, adjList, myStack); 
     } 
     curr = curr->next; 
    } 
    myStack.push(v); 
} 

и, казалось, работать для моих целей. Но мне сложно перевести его в итерационное решение. Это моя попытка:

void dfs(int v, bool visited[], node* adjList[], std::stack<int> &myStack) { 
    std::stack<int> recursion; 
    visited[v] = true; 

    recursion.push(v); 

    while(!recursion.empty()) { 
     v = recursion.top(); 
     recursion.pop(); 
     node* curr = adjList[v]; 

     myStack.push(v); 

     while (curr != NULL) { 
      if(!visited[curr->val]) { 
       visited[curr->val] = true; 
       recursion.push(curr->val); 
      } 
      curr = curr->next; 
     } 
    } 
} 

Но заказ полностью испорчен! Я думаю, что это может быть связано с позиционированием моего myStack.push(v), но я не знаю, как подойти к этому. Любая помощь была бы оценена.

Answer 1

Я думаю, что решил свою проблему. По сути, вы можете получить топологический порядок, отсортировав узлы к моменту их завершения. Но вместо того, чтобы выполнять сортировку и получение решения O (nlogn), мы можем сохранить это как O (n). Когда вы закончите с узлом, вместо записи времени окончания, мы можем выставить уникальный идентификатор узла в стек. Поскольку мы имеем дело только с положительными вершинами в моем случае, достаточно будет сделать уникальный идентификатор просто отрицательным значением вершин. Таким образом, если мы последовательно выходим из нашего стека, мы получим наш топологический порядок.

void dfs(int v, bool visited[], node* adjList[], std::stack<int> &myStack) { 
    std::stack<int> recursion; 
    visited[v] = true; 
    recursion.push(v); 

    while(!recursion.empty()) { 
     v = recursion.top(); 
     recursion.pop(); 

     //A dummy node to denote finish order (e.g. topological order) 
     if (v < 0) { 
      myStack.push(v * -1); 
     } else { 
      node* curr = adjList[v]; 
      recursion.push(v * -1); 

      while (curr != NULL) { 
       if(!visited[curr->val]) { 
        visited[curr->val] = true; 
        recursion.push(curr->val); 
       } 
       curr = curr->next; 
      } 
     } 
    } 
}