обратных упорядоченного обход графа

Question

Этот вопрос является результат странного поведения, которое я получаю из ДФСА обхода графа algorithm.i пытался реализовать DFS и вот мой код для него:

#include<iostream> 
#include<stack> 
#include<vector> 
#include<map> 

using namespace std; 
map<int,bool> discovered; 

map< int , vector<int> > graph { 
    {1,{2,3}}, 
    {2,{1,4,5}}, 
    {3,{1}}, 
    {4,{2}}, 
    {5,{2}} 
}; 

vector <int> visited; 
void clear_graph(){ 
for(map<int,bool>:: iterator iter = discovered.begin(); iter != discovered.end(); iter++) 
    discovered[iter->first] = false; 
} 


void dfs(int start) {  
    int current; 
    int next; 
    unsigned int i; 
    stack <int> vertices; 
    discovered[start] = true; 
    vertices.push(start); 

    while (!vertices.empty()){ 
     current = vertices.top(); 
     visited.push_back(current); 
     vertices.pop(); 
     for(i = 0 ; i<graph[current].size() ; i++){ 
      next = graph[current][i]; 
      if (!discovered[next]){ 
       discovered[next] = true; 
       vertices.push(next); 
      } 
     } 
    } 
} 

int main() {  
    clear_graph(); 
    int start = 1; 
    dfs(start); 

    vector<int> ::iterator vi; 
    for(vi=visited.begin(); vi!=visited.end();vi++) 
     cout<<*vi<<" "; 

    return 0; 
} 

Это это граф я рассматриваю:

выход на графике: 1->2->4->5->3 но выход я получаю: 1->3->2->5->4

Я могу заметить, что это также действительный обход DFS, но справа налево oredr, почему это так? если не так, какая часть моего кода я ошибаюсь? и этот множественный обход одного графика не приведет к неправильным результатам в случаях, когда требуется обход DFS?

Answer 1

Это просто вопрос разницы в алгоритме.

Если вы делаете это рекурсивно, вы должны перебрать 2 полностью, прежде чем будете делать резервную копию до 3, следовательно 1->2->4->5->3. Если вы сделаете это итеративно, вы бы посетили соседей в обратном порядке, так что сначала вы закончите сначала итерацию 3, следовательно, 1->3->2->5->4. Ваш алгоритм по-прежнему является правильным алгоритмом поиска по глубине, который отличается от того, который использовал изображение.

Если вы хотите сохранить свое итерационное решение, но получите тот же результат, что и рекурсивный, вы можете просто отменить свой заказ. Изменение:

next = graph[current][i]; 

к:

next = graph[current][graph[current].size() - i - 1]; 

Answer 2

Ваш обходом сторнируется, потому что вы используете структуру данных стека, который выскакивает элементы в обратном порядке (Last-In-First-Out), как они были вытеснены в стек. Вы нажимаете вершины в стек вперед, поэтому вы получаете их из стека назад.

Вот встроенные комментарии, объясняющие, почему реверсирование обхода происходит:

void dfs(int start) {  
    int current; 
    int next; 
    unsigned int i; 
    stack <int> vertices; 
    discovered[start] = true; 
    vertices.push(start); 

    while (!vertices.empty()){ 
     // here you pop vertices from the stack in the reverse order of how 
     // the vertices were pushed into the stack 
     current = vertices.top(); 
     visited.push_back(current); 
     vertices.pop(); 
     // here you traverse the vertices forward 
     for(i = 0 ; i<graph[current].size() ; i++){ 
      next = graph[current][i]; 
      if (!discovered[next]){ 
       discovered[next] = true; 
       // here you push vertices into the stack 
       vertices.push(next); 
      } 
     } 
    } 
} 

Answer 3

Вы подталкиваете ребенок-узлы в стек в порядке слева направо. В результате, правый узел будет всплывать и обрабатываться первым. Для перемещения детей в порядке слева направо:

for (int i = graph[current].size()-1; i >= 0; --i)