Почему ДФС с использованием стека не дает правильный результат

Question

See DFS image Here

Я использую стек для печати последовательность ДФС. Согласно входу и этому изображению графика последовательность 1 2 4 8 5 6 3 7. Но мой код дает результат как 1 2 4 8 7 6 5 3. Может кто-нибудь объяснить, как я могу это исправить ??

 

Input: 
8 10 
1 3 
1 2 
2 5 
2 4 
3 7 
3 6 
4 8 
5 8 
6 8 
7 8 


Correct Output: 

Sequence: 1 2 4 8 5 6 3 7 

Мой код:

#include <bits/stdc++.h> 
using namespace std; 
vector<int>edges[100]; 
stack<int>q; 
vector<int>item; 
int level[100],parent[100],visited[100],tn; 



void dfs(int s) 
{ 
    int j,k,fr; 
    q.push(s); 
    level[s]=0; 
    for(j=1;j<=tn;j++) 
    { 
     visited[j]=0; 
    } 
    visited[s]=1; 
    while(!q.empty()) 
    { 
     fr=q.top(); 
     q.pop(); 
     item.push_back(fr); 
     for(k=0;k<edges[fr].size();k++) 
     { 
      if(visited[edges[fr][k]]==0) 
      { 
       q.push(edges[fr][k]); 
       //cout<<"Pushed="<<fr<<"="<<edges[fr][k]; 
       visited[edges[fr][k]]=1; 
      } 


     } 

     //cout<<endl; 



    } 
} 


int main() 
{ 
    int i,e,p,n,u,v,f,m; 
    cin>>tn>>e; 
    for(i=1;i<=e;i++) 
    { 
     cin>>u>>v; 
     edges[u].push_back(v); 
     edges[v].push_back(u); 
    } 
    dfs(1); 
    cout<<"Sequence="<<endl; 
    for(m=0;m<item.size();m++) 
    { 
     cout<<item[m]; 
    } 
    return 0; 
} 

Мой код показывает этот выход: 1 2 4 8 7 6 5 3

Answer 1

Маркировка узлов, как побывал в реализации содержит ошибку; функцию можно переписать следующим образом.

void dfs(int s) 
{ 
    int j, k, fr; 
    q.push(s); 
    level[s] = 0; 
    for (j = 1; j <= tn; j++) 
    { 
     visited[j] = 0; 
    } 
    while (!q.empty()) 
    { 
     fr = q.top(); 
     q.pop(); 
     if (0 == visited[fr]) 
     { 
      visited[fr] = 1; 
      item.push_back(fr); 
      for (k = 0; k < edges[fr].size(); k++) 
      { 
       q.push(edges[fr][k]); 
      } 
     } 
    } 
} 

В этой версии узел получает отметку только в том случае, если он взят из стека. Обратите внимание, что проверка того, был ли узел уже посещен, необходим, поскольку узел в стеке может быть посещен последующей итерацией. Эта реализация дает последовательность

1 2 4 8 7 3 6 5 

, который, однако, не является тем, который описывается как желаемое решение. Однако обратите внимание, что без дополнительных правил тай-брейка алгоритм DFS допускает некоторую двусмысленность в последовательности посещений. Последовательность

1 2 4 8 5 6 3 7 

могут быть сгенерированы нажатием соседа с наименьшим идентификатором в стек последним, заставляя его посетить в следующей итерации.