C 中的 BFS 遍历 - 代码未按预期工作

Question

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

struct queue
{
    int size;
    int f;
    int r;
    int* arr;
};

int isEmpty(struct queue *q){
    if(q->r==q->f){
        return 1;
    }

    return 0;
}

int isFull(struct queue *q){
    if(q->r==q->size-1){
        return 1;
    }
    return 0;
}

void enqueue(struct queue *q, int val){
    if(isFull(q)){
        printf("This Queue is full\n");
    }
    else{
        q->r++;
        q->arr[q->r] = val;
        // printf("Enqued element: %d\n", val);
    }
}

int dequeue(struct queue *q){
    int a = -1;
    if(isEmpty(q)){
        printf("This Queue is empty\n");
    }
    else{
        q->f++;
        a = q->arr[q->f]; 
    }
    return a;
}

int main(){
    // Initializing Queue (Array Implementation)
    struct queue q;
    q.size = 400;
    q.f = q.r = 0;
    q.arr = (int*) malloc(q.size*sizeof(int));

    // BFS Implementation 
    int node;
    int i = 1;
    int visited[7] = {0,0,0,0,0,0,0};
    int a [7][7] = {
        {0,1,1,1,0,0,0},
        {1,0,1,0,0,0,0},
        {1,1,0,1,1,0,0},
        {1,0,1,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} 
    };

    printf("%d", j)

    visited[i] = 1;
    enqueue(&q, i); // Enqueue i for exploration
    while (!isEmpty(&q))
    {
        int node = dequeue(&q);
        for (int j = 0; j < 7; j++)
        {
            if(a[node][j] ==1 && visited[j] == 0){
                printf("%d", j);
                visited[j] = 1;
                enqueue(&q, j);
            }
        }
    }
    return 0;
}

我试图获得

BFS

遍历，但输出没有出现，伴随着不合时宜的崩溃和错误，我正在使用基于数组的队列在 C 中实现

BFS

遍历。

代码可以编译，但输出不符合预期。该程序旨在对邻接矩阵表示的图执行

BFS

遍历，但输出与预期的

BFS

遍历顺序不匹配。

Answer 1

如果我从程序中删除第一行

printf("%d", j)

，那么它会正确编译并运行（打印正确的输出）。

你的图表

a

：

    int a [7][7] = {
        {0,1,1,1,0,0,0},  // 0 --> 1, 2, 3
        {1,0,1,0,0,0,0},  // 1 --> 0, 2
        {1,1,0,1,1,0,0},  // 2 --> 0, 1, 3, 4
        {1,0,1,0,1,0,0},  // 3 --> 0, 2, 4
        {0,0,1,1,0,1,1},  // 4 --> 2, 3, 5, 6
        {0,0,0,0,1,0,0},  // 5 --> 4
        {0,0,0,0,1,0,0}   // 6 --> 4
    };

BFS从节点1开始：

    visited[i] = 1;
    enqueue(&q, i); // Enqueue i for exploration

程序输出：

023456

程序输出中缺少初始节点 1。如果您需要，请执行上面的

printf

而不是

dequeue

。为什么输出正确？

距起点距离为 0 的节点：1

• 距起点距离为 1 的节点：0, 2
• 距起点距离为 2 的节点：3
• 距起点距离为 3 的节点：4
• 距起点距离为 4 的节点：5、6