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

Question

我正在解决一个允许两种类型的运算的问题：从一个数字中减去一个或将其乘以2，并提供源和目标数字。两个数字的输入约束均为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变量不代表最小的操作数，它代表您从队列中检索元素的次数。您需要为每个新级别增加它。

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

UPD。另外，您将0指定为已访问，但是您从未处理过10^4的上限，因此节点将被无限地乘以2，并且队列将用尽内存。因此，要么将所有大于10^4的节点标记为已访问，要么需要检查g[u][j]最多为10^4]内的[C0