Logical Bugs in my naive BFS Implementation

Could someone please tell the mistake in my logic in using BFS to compute shortest distance of a node from a given starting node using adjacency list on an undirected graph?

void bfs(int s) {
dist[s] = 0;
queue<int> q; q.emplace(s);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int i = 0; i < adj_list[u].size(); ++i) {
        if (dist[adj_list[u][i]] == -1) {
            dist[adj_list[u][i]] = 1 + dist[u];
            q.emplace(adj_list[u][i]);
        }
    }
}

}

All distances are set to -1 before starting this algorithm.

Are the sample inputs also getting WA

void bfs(struct node **a,int n,int v)
{
int u,w;
struct node *temp;
u=v;
do
{
if(visited[u]==0)
{
temp=a[u];
visited[u]=1;
}
//for all w adj from u
while(temp!=NULL)
{
w=temp->data;
temp=temp->next;
if(visited[w]==0)
{
//add w to q[]
rear++;
q[rear]=w;
printf("%d\t",w);
visited[w]=1;
}
}
if(rear==front)
return;
front++;
u=q[front];
temp=a[u];

}while(1);

}

@teracoder can you give your full code?

1 Like

Your code will run indefinitely.

Just make a bool array ‘visited[size]’ to track the nodes. Mark all it’s elements to 0 initially indicating no nodes are visited.

Now add two more lines to your bfs function.

  1. Before while loop visited[s]=1

  2. Inside the ‘if’ block visited[i]=1

And modify it’s condition as if(your condition&&visited[i]==0) { }

Instead of making a boolean array he has just made a distance array in which if not visited means -1.

1 Like

Ok I understood why it happened. I checked your code you at commonlounge community and the reason it is giving WA is that you have you have not set all dist[i] to -1. You have done -

int dist[3500] = {-1};

This only gives the value -1 to dist[0]. To fill the array with -1, you either need to do -

fill(dist,dist+3500,-1);

Or

for (int i = 0; i < 3500; i++) dist[i] = 3500;

Edit -

Here’s your corrected code -

int dist[3500];
for (int i = 0; i < 3500; i++) dist[i] = -1;

void bfs(int s) {
    dist[s] = 0;
    queue<int> q; q.emplace(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < adj_list[u].size(); ++i) {
            if (dist[adj_list[u][i]] == -1) {
                dist[adj_list[u][i]] = 1 + dist[u];
                q.emplace(adj_list[u][i]);
            }
        }
    }    
}
1 Like

Should have assumed that there are no such shortcuts, sorry. Also learnt that its the same as initialising everything else as zero. Thank you!

The fill syntax shows errors. Any idea? Sorry, I haven’t used C style arrays much.

For vectors you can use fill(v.begin(),v.end(),-1) and you can also do array.fill(-1) for arrays.

Some links -
http://www.cplusplus.com/reference/array/array/fill/
http://www.cplusplus.com/reference/algorithm/fill/

1 Like

you need to include the algorithm header file

I’ve used them for vectors but not C style arrays

The one you’ve given is for std::array which I haven’t used, OK will switch it now.

fill_n also doesn’t work. Switching to C++11 array<T,N>. EDIT: That too didn’t work.

All of these are supposed to work; but why isn’t it?

I’ve declared it out of main; maybe that’s why, is it?

Finally, done; enough said for a little lack of C++ knowledge to great chaos. Don’t call a function before main else end up debugging.

When I got to know about fill, it happened with me as well

Huh, great failing the last test case, must be something

//