c++ - BFS traverses graph node twice -

i have trouble finding bug in code of mine node in graph appears twice.i have used vector storing relationship between edges. highly appreciated.

#include<bits/stdc++.h> using namespace std; int main(){     int n,m;     cin>>n>>m;     vector<int> v[n+1];     (int = 0; < m; ++i)     {         int a,b;         cin>>a>>b;         v[a].push_back(b);         v[b].push_back(a);     }     std::queue<int>q ;     q.push(1);     cout<<"and traversal is:\n";     bool visited[n+1]={false};     for(;!q.empty();){         int curr=q.front();         q.pop();         cout<<curr<<endl;         for(int i=0;i<v[curr].size();++i){             if(!visited[v[curr][i]]){                 q.push(v[curr][i]);                 visited[curr]=true;             }         }     } } 

the input checked against:

5 5 1 3 3 2 2 4 3 5 5 4 

output:

and traversal is: 1 3 2 5 4 4 

you need distinguish 3 states node can in:

• unprocessed (not yet seen)
• discovered (queued)
• processed (traversed, outputted)

with visited boolean array might either tag nodes when discovered or when have been traversed. while term "visited" refers latter, using former means nodes not added multiple times queue , don't need if (visited[curr]) continue; check.

so right, you'll need fix 2 things in code:

• the start node (1) initialises queue discovered definition
• in loop on neighbors of current node, mustn't tag visited[curr] neighbor "discovered" when add queue

cout<<"and traversal is:\n"; std::queue<int>q; bool visited[n+1]={false}; q.push(1); visited[1] = true; while(!q.empty()){     int curr=q.front();     q.pop();     cout<<curr<<endl;     for(int i=0;i<v[curr].size();++i){         int target = v[curr][i]; // opposite node on edge          if(!visited[target]){             q.push(target);             visited[target]=true;         }     } } 

---

old (incomplete) answer below
you want set current node visited always, not when has neighbor unvisited yet (4 doesn't have neighbors in fact). move outside of loop:

for(int i=0;i<v[curr].size();++i){     if(!visited[v[curr][i]]){         q.push(v[curr][i]);     } } visited[curr]=true; 

possibly should move in front of loop, in case there self-loop edges.