我正在尝试在 C 中使用邻接矩阵实现 BFS，但是我的代码没有在第一行之后处理出队函数

Question

我正在使用邻接矩阵在 C 语言中实现 BFS。我正在使用队列（链接列表）来执行入队和出队操作。我的代码正在使第一个顶点出队，即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

我是如何调试它的：
向外部作用域添加一个 static int 计数器。
当你在 q 上放置一个项目时增加计数器。
当您从 q 中删除一个项目时减少计数器。
在出队时验证 (front == NULL) == (counter == 0) -- 这些条件必须相同。否则报错。 man 3 assert 以更简洁的方式执行此操作。
在 isEmpty() 中，也验证相同的条件。

它立即注意到 front 为 0 而 count 为 2。在出列中，您检查条件：

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

然而当你删除一个节点时，你永远不会更新 rear。将前面的弹出更改为：

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

似乎可以为您解决问题。注意，你费心写一个 "isEmpty()"，为什么不在入队和出队中使用它呢？以下：

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

比

有更好的记录

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

我正在尝试在 C 中使用邻接矩阵实现 BFS，但是我的代码没有在第一行之后处理出队函数

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

c

queue

graph

breadth-first-search

adjacency-matrix