CODEWITHSUNDEEP
c++algorithmgraphshortest-pathbreadth-first-search
FoxyZ
FoxyZ

Reputation: 176

Infinite loop in my BFS function

I'm trying to implement the BFS algorithm in C++ to find the distance of each node from a source vertex (e.g 0), But it seems like there's an infinite loop in my function. After some debugging I found out that all nodes get visited but my queue never gets empty. Why is that?

#include <bits/stdc++.h>

using namespace std;

int d[1000];
int visited[1000];
vector <int> adj[1000];

queue<int> que;

void bfs(int source)
    {
        d[source]=0;
        visited[source]=1;
        que.push(source);
        while(!que.empty())
        {
            int current = que.front();
            que.pop();
            for (int i=0;i<adj[current].size();i++)
                {
                    int v=adj[current][i];
                    if(visited[v]!=1);
                    { 
                        visited[v]=1;
                        d[v]=d[current]+1;
                        que.push(v);
                    }
                }
        }
    }
int main(){
    int E,start,end,n;
    cin >> n >> E;
    for (int i=0;i<n;i++)
            d[i]=-1;
    for (int i=0;i<n;i++)
            visited[i]=0;
    for (int i=0;i<E;i++)
        {
            cin >> start >> end;
            adj[start].push_back(end);
            adj[end].push_back(start);
        }
    bfs(0);
    for (int i=0;i<n;i++)
        cout << "d" << i << "= " << d[i] << endl;
    return 0;
}

Upvotes: 3

Views: 672

Answers (1)

user007
user007

Reputation: 2172

The only error I see is ::

if(visited[v]!=1);

A semicolon is all you need to remove!! :D

Upvotes: 6

Related Questions