在C中使用队列和邻接表实现BFS

Question

我正在解决一个允许两种类型的操作的问题：从数字中减去一个或将其乘以二，并提供源和目标数字。两个数字的输入约束均为 1<=n<=10^4。我应该输出从给定的产生所需数量所需的操作数。以下是我的实现，出现运行时错误，显然，我不知道为什么。如果有人解释这个错误，那就太棒了。谢谢

#include <stdio.h>
#include <stdlib.h>
int g[22222][3], v[2222], size;//g == graph, v == visited and size == the size of queue
typedef struct _queue
{
    int val;
    struct _queue *next;
    struct _queue *prev;
} queue;
queue *head=NULL, *last=NULL;
void push(int val)
{
    queue *ptr=(queue *) malloc(sizeof(queue));
    ptr->next=NULL;
    ptr->val=val;
    if (head)
    {
        last->next=ptr;
        ptr->prev=last;
    }
    else
    {
        head=ptr;
        ptr->prev=NULL;
    }
    last=ptr;
}
void pop()
{
    if (size)
    {
        queue *ptr=last;
        last=last->prev;
        if (head) last->next=NULL;
        free(ptr);
    }
}
int front() {return last->val;}
int bfs(int s, int d)//s == source and d == destination
{
    int cnt=0;
    push(s);
    size++;
    v[s]=1;
    while (size)
    {
        int u=front();
        pop();
        size--;
        for (int j=1; j<=2; j++)
        {
            if (d==g[u][j]) return (cnt+1);
            if (!v[g[u][j]])
            {
                v[g[u][j]]=1;
                size++;
                push(g[u][j]);
            }
        }
        cnt++;
    }
}
int main()
{
    int n, m, val;
    scanf("%d%d", &n, &m);
    if (n==m) {printf("0"); return 0;}
    val=(n>m?n:m)*2;
    v[0]=1;
    for (int i=1; i<=val; i++)
    {
        g[i][1]=2*i;
        g[i][2]=i-1;
    }
    printf("%d", bfs(n, m));
    return 0;
}

Answer 1

您已经实现了一个堆栈，即 LIFO（后进先出）：您正在添加到末尾并从末尾检索。

你应该实现一个队列，即 FIFO（先进先出），所以如果你添加到末尾，你应该从前面检索：

void pop()
{
    if (size)
    {
        queue *ptr=head;
        head=head->next;
        if (head) head->prev=NULL;
        free(ptr);
    }
}
int front() 
{
   return head->val;
}

此外，我猜您的目标是计算从给定的操作生成所需数字所需的最小操作次数。您的 cnt 变量并不代表最少的操作次数，它代表您从队列中检索元素的次数。您需要为每个 新级别 增加它。

最后，即使没有从 s 到 d 的路径，您的 bfs 也应该 return 一个值，因此您应该将 return 0; 放在后面while(size){} 循环。

更新。如果 bfs 内的 2 * (10^4) 大于 2 * (10^4)，则需要跳过 g[u][j]，否则这些值将被排队，这是对 space 的浪费。顺便说一句，你的 v 数组只有 2222 个元素，它应该至少有 20001 个（v[20000] 是最后一个）

在C中使用队列和邻接表实现BFS

Implementation of BFS using queue and adjacency list in C

c

queue

graph

breadth-first-search