Я пытаюсь реализовать BFS, используя матрицу смежности в C, но мой код не обрабатывает функцию удаления из очереди после первой строки

Question

Я реализую BFS на языке C с использованием матрицы смежности. Я использую очереди (связанный список) для выполнения операций постановки и удаления из очереди. Мой код удаляет первую вершину, то есть 1, но после того, как соседние вершины до 1, то есть 2 и 3 помещаются в очередь, но не удаляются из очереди, из-за чего мой дисплей дает 1 2 3 в качестве вывода, а не остальные вершины которые не являются смежными с 1. Отображается график, для которого я делаю BFS, и его матрица смежности была создана в основной функции.

#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

• Как я его отлаживал:
• Добавить счетчик stati c int во внешнюю область.
• Увеличивать счетчик, когда вы помещаете элемент в q.
• Уменьшает значение счетчика, когда вы удаляете элемент из q.
• Проверяйте при удалении из очереди, что (front == NULL) == (counter == 0) - эти условия должны быть одинаковыми . В противном случае сообщите об ошибке. man 3 assert для более аккуратного способа сделать это.
• В isEmpty () также проверьте то же условие.

Он сразу заметил, что front был 0, а count был 2. В dequeue, вы проверяете условие:

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

но когда вы удаляете узел, вы никогда не обновляете задний. Изменение всплывающего окна на:

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

, похоже, исправляет это прямо для вас. Обратите внимание, вы потрудились написать isEmpty (), почему бы не использовать его в enqueue и dequeue? Следующее:

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

гораздо лучше документировано, чем:

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