c - BFS上的无限循环

我正在尝试创建一个程序，该程序查找节点B是否从节点A开始属于该子树。我用C语言编写了代码，并自实现了一种队列机制，因为我正在使用BFS遍历树。问题是我的代码遇到一个无限循环，说我的队列已满甚至没有。

码：

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


#define MAXSIZE 6
typedef struct Queue
{
    int capacity;
    int size;
    int front;
    int rear;
    int * elements;
}Queue;
Queue * createQueue(int maxElements)
{
    Queue *q;
    if (NULL != (q = (Queue *)malloc(sizeof(Queue))))
    {
        q->elements = (int*)malloc(maxElements * sizeof(int));
        q->size = 0;
        q->capacity = maxElements;
        q->front = 0;
        q->rear = -1;
        return q;
    }
}


void dequeue(Queue *q)
{
    if (0 == q->size)
    {
        printf("Queue is empty\n");
        return;
    }
    else
    {
        q->size--;
        q->front++;
        if (q->front == q->capacity)
        {
            q->front = 0;
        }
    }
}


int front(Queue *q)
{
    if (q->size == 0)
    {
        printf("queue is empty\n");
        exit(0);
    }
    return q->elements[q->front];
}


void enqueue(Queue *q, int element)
{
    if (q->size == q->capacity)
    {
        printf("queue is full \n");
    }

    else
    {
        q->size++;
        q->rear++;
        if (q->rear == q->capacity)
        {
            q->rear = 0;
        }
        q->elements[q->rear] = element;
    }
    return;
}



void readInput(int A[],int B[],int M[][MAXSIZE],int N)
{
    FILE * fp;
    int row, col;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            M[i][j] = 0;
    if (0 == fopen_s(&fp,"input.txt", "r"))
    {
        fscanf_s(fp, "%d", &N);
        for (int i = 0; i < N; i++)
            fscanf_s(fp,"%d ", &A[i]);
        for (int i = 0; i < N; i++)
            fscanf_s(fp,"%d ", &B[i]);


        for (int i = 0; i < N; i++)
        {
            fscanf_s(fp, "%d %d", &row,&col);
            M[row][col] = 1;
        }

    }

}

bool vBelongsToUSubtree(int M[][MAXSIZE], int *u, int* v)
{
    bool belongs = false, visited[MAXSIZE];
    for (short i = 0; i < MAXSIZE; i++)visited[i] = false;
    visited[*u] = true;
    Queue *q = createQueue(MAXSIZE);
    enqueue(q, *u);
    printf("%d\n", front(q));
    int node;
    while (0 != q->size)
    {
        node = front(q);
        dequeue(q);
        for (int i = 1; i < MAXSIZE; i++)
        {
            if (1 == M[node][i] and false == visited[i])
            {
                enqueue(q, node);
                visited[node] = true;
                if (node == *v)return true;
            }
            //printf("!\n");
        }
        //printf("%d\n", node);

    }
    /*for (int i = 0; i < q->size; i++)
    {
        printf("%d \n", front(q));
    }

*/
    return belongs;
}

int main()
{
    int A[100], B[100], M[MAXSIZE][MAXSIZE], N=0;
    readInput(A, B, M, N);
    for(int i=1;i<=MAXSIZE;i++)
        for(int j=i;j<=MAXSIZE;j++)
             if(vBelongsToUSubtree(M, &i, &j))printf("yes");
             else printf("not");
    system("pause");

    return 0;
}

最佳答案

如注释中所指出，现有代码存在一些问题。在完全无法使用之前，您应该解决它们。

此答案仅解决您询问的无限循环...

同时在评论中指出：

如果以下语句中的i或j未被正确控制，它们可能永远不会满足if(vBelongsToUSubtree(M, &i, &j))printf("yes");或for(int i=1;i<=MAXSIZE;i++)中的退出条件

跟随for(int j=i;j<=MAXSIZE;j++)直到其执行流程结束，它似乎已经出现了（也许i从未被更改。

传递j)的电话链：

if(vBelongsToUSubtree(M, &i, &j))printf("yes");

依次调用：

enqueue(q, *u);

里面有原型：

void enqueue(Queue *q, int element)

其中i是int element的值，并且不会更改。 （也不能使用此原型。）

关于c - BFS上的无限循环，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57710117/