Logical Bugs in my naive BFS Implementation

general
,
1

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.

2

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);

}

3

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) { }

4

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
5

Are the sample inputs also getting WA

6

@teracoder can you give your full code?

1 Like
7

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

1 Like
8

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

9

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

10

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

11

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

1 Like
12

you need to include the algorithm header file

13

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

14

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

15

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

16

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

17

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

18

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.

19

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

20

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