I am trying to implement BFS using adjacency matrix in C,but my code is not processing the dequeue function after the first row

Question

I am implementing BFS in C language using adjacency matrix. I am using queues(linked list) to perform the enqueue and dequeue operations. My code is dequeuing the first vertex,i.e. 1 but after than the adjacent vertices to 1, i.e 2 & 3 are getting enqueued but not getting dequeued due to which my display is one giving 1 2 3 as output and not the rest of the vertices which are not adjacent to 1. The graph for which I am doing BFS is shown and its adjacency matrix has been created in the main function.

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *next;
}*front=NULL,*rear=NULL;

void enqueue(int x)
{
    struct node *t;     //temporary node for addition of new node
    t=(struct node*)malloc(sizeof(struct node));
    if(t==NULL)         //Heap is full
        printf("Queue is full\n");
    else
    {
        t->data=x;
        t->next=NULL;
        if(front==NULL && rear==NULL)   //queue is empty
            front=rear=t;       //only one element in linked list
        else
        {
            rear->next=t;
            rear=t;
        }
    }
    //printf("Vertex enqueued %d \n",t->data);
    //printf("Rear pointing at %d \n",rear->data);
}

int dequeue()
{
    int x=-1;
    struct node *t;
    if(front==NULL && rear==NULL)
        printf("Queue is empty\n");
    else
    {
        t=front;
        front=front->next;
        x=t->data;
        free(t);
    }
    //printf("Vertex dequeued %d \n",x);
    //printf("Front pointing at %d \n",front->data);
    return x;
}

int isEmpty()
{
    if(front==NULL)
        return 1;
    else
        return 0;
}

void BFS(int G[][7],int start,int n)    //n-dimension
{
    int i=start;        //starting index 
    int visited[7]={0};
    printf("%d ",i);
    visited[i]=1;       
    enqueue(i);
    while(!isEmpty())
    {
        i=dequeue();            //control is not going back here after dequeueing 1. 2 & 3 getting enqueued but are not getting dequeued.
        for(int j=1;j<=n;j++)
        {
            if(G[i][j]==1 && visited[j]==0)
            {
                printf("%d ",j);
                visited[j]=1;
                enqueue(j);
            }
        }
    }
}
int main()
{
    int G[7][7]={{0,0,0,0,0,0,0},
                 {0,0,1,1,0,0,0},
                 {0,1,0,0,1,0,0},
                 {0,1,0,0,1,0,0},
                 {0,0,1,1,0,1,1},
                 {0,0,0,0,1,0,0},
                 {0,0,0,0,1,0,0}};
    BFS(G,1,7);

    return 0;
}

Answer 1

• How I debugged it:
• Add a static int counter to the outer scope.
• Increment the counter when you put an item on the q.
• Decrement the counter when you remove an item from the q.
• Verify, in dequeue, that (front == NULL) == (counter == 0) -- these conditions must be the same. Report an error otherwise. man 3 assert for a tidier way to do this.
• In isEmpty(), also verify the same condition.

It immediately noted that front was 0 while count was 2. In dequeue, you check the condition:

if(front==NULL && rear==NULL)

yet when you remove a node, you never update rear. Changing the popping of front to:

if ((front=front->next) == NULL) {
    rear = NULL;
}

seems to fix it right up for you. Note, you bothered to write an "isEmpty()", why not use it in enqueue & dequeue? The following:

if (isEmpty()) {
    front = rear = t;
}

is much better documented than:

if (front==NULL && rear == NULL) // queue is empty
    front = rear = t;