CODEWITHSUNDEEP
c++breadth-first-search
Siva Prasad
Siva Prasad

Reputation: 753

BFS traverses graph node twice

I have trouble finding bug in this code of mine where a node in the graph appears twice.I have used vector for storing the relationship between the edges. Any help is highly appreciated.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> v[n+1];
    for (int i = 0; i < 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 the 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 with which I checked against:

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

Output:

And the traversal is:
1
3
2
5
4
4

Upvotes: 0

Views: 791

Answers (1)

Bergi
Bergi

Reputation: 664503

You will need to distinguish three states that a node can be in:

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

With the visited boolean array you might either tag nodes when they are discovered or when they have been traversed. While the term "visited" usually refers to the latter, using the former means that nodes are not added multiple times to the queue and don't need an extra if (visited[curr]) continue; check.

So to get this right, you'll need to fix two things in your code:

  • The start node (1) which initialises the queue is already discovered by definition
  • In the loop over the neighbors of the current node, you mustn't tag visited[curr] but actually the neighbor as "discovered" when you add it to the queue

cout<<"And the 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 to set the current node to visited always, not only when it has a neighbor that is unvisited yet (4 doesn't have any neighbors in fact). Move that outside of the loop:

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

Possibly you even should move it in front of the loop, just in case there are self-loop edges.

Upvotes: 2

Related Questions