Программа обхода BFS в c с использованием очереди

Question

В данный момент я изучаю графики и использую C. Когда я представляю график со списком смежности, мне нужна очередь для прохождения BFS.Однако у меня возникли некоторые проблемы с кодом - я не уверен, правильно ли я понял концепцию обхода bfs с очередями.

Я вставил прокомментированный код ниже, надеюсь, он читабелен.Может кто-нибудь проверить это или хотя бы предоставить некоторую информацию о том, как правильно это сделать?

программа аварийно завершает работу и также показывает ошибку сегментации

#include<stdio.h>
#include<stdlib.h>
struct Queue{
    int rear;
    int front;
    int capacity;
    int* array;
};
struct adjlistnode{
    int dest;
    struct adjlistnode* next;
};
struct adjlist{
    struct adjlistnode* head;
};
struct graph{
    int V;
    struct adjlist* array;
};
int visited[100];

struct Queue* createqueue(int capacity){
    struct Queue* queue=(struct Queue*)malloc(sizeof(struct Queue));
    queue->rear = -1;
    queue->front = -1;
queue->capacity=capacity;
queue->array=(int*)malloc(sizeof(int)*capacity);
return queue;
}
int isempty(struct Queue* queue){
    return(queue->front==-1 && queue->rear==-1);
}
void enqueue(struct Queue* queue,int data){
    if(isempty(queue)){
        queue->rear=0;
        queue->front=0;
        queue->array[queue->rear]=data;
        printf("%d",queue->array[queue->rear]);
        return;
    }
queue->rear=(queue->rear+1)%queue->capacity;
queue->array[queue->rear]=data;
} 
int dequeue(struct Queue* queue){
    if(isempty(queue))
        return -1;
    int temp=queue->front;
    queue->front=(queue->front+1)%queue->capacity;
    return (queue->array[temp]); 
}
int isfront(struct Queue* queue){
    return(queue->array[queue->front]);
}
/// GRAPH FUNCTIONS
struct adjlistnode* getnewnode(int dest){
    struct adjlistnode* newnode =(struct adjlistnode*)malloc(sizeof(struct adjlistnode));
    newnode->dest=dest;
    newnode->next=NULL;
    return newnode;
}
struct graph* creategraph(int V){
    struct graph* G = (struct graph*)malloc(sizeof(struct graph));
    G->V=V;
    G->array=(struct adjlist*)malloc(V*sizeof(struct adjlist));
    for(int i=0;i<V;i++){
        G->array[i].head=NULL;
    }
 return G;
}
void addedge(struct graph* G,int src ,int dest){
    struct adjlistnode* newnode=getnewnode(dest);

    newnode->next=G->array[src].head;
    G->array[src].head=newnode; 

    newnode=getnewnode(src);

    newnode->next=G->array[dest].head;
    G->array[dest].head=newnode;
}
void printgraph(struct graph* G){
    for(int i=0;i<G->V;i++){
        struct adjlistnode* temp=G->array[i].head;
        while(temp!=NULL){
            printf("%d",temp->dest);
            temp=temp->next;
        }
        printf("\n");
    }
}
void bfs(struct graph* G,struct Queue* queue,int startvertex){


    enqueue(queue,startvertex);


    while(!isempty(queue)){
       int u=dequeue(queue);
       visited[u]=1;
       printf(" \n %d ",u);
       struct adjlistnode* temp=G->array[u].head;
       while(temp){
         if(visited[temp->dest]==0){
             visited[temp->dest]=1;
             enqueue(queue,temp->dest);
          }
       temp=temp->next;
       }

    }

}
void bfstraversal(struct graph* G,struct Queue *queue){
    int i;
    for(i=0;i<G->V;i++)
        visited[i]=0;
    for(i=0;i<G->V;i++){
        if(!visited[i]){
            bfs(G,queue,i);
        }
    }
}
 int main(){
    struct Queue* queue=createqueue(100);


    struct graph* G=creategraph(5);
    addedge(G,1,2);
    addedge(G,1,1);
    printgraph(G);
    bfstraversal(G,queue);
  //  printf("\n%d",dequeue(queue));
}

Answer 1

Ваш bfs работает нормально, как отмечали люди, ваша функция isEmpty () для очереди имеет недостаток.Следует проверить 2 условия:

1. Ни один элемент не был помещен в очередь или снят с очереди до сих пор.Для этого условие:
   (queue->front==-1 && queue->rear==-1)

2. Все элементы в очереди были сняты с очереди, например, в очереди вы поставили в очередь 2, 3, затем тыл = 0 ифронт = 1.Теперь вы удалили из очереди 2 элемента, в результате чего очередь пуста, а задний = 2 и передний = 1.Это тот случай, когда задняя часть превышает переднюю.Вы должны проверить условие, когда разница между передним указателем и задним указателем равна 1.

   ((queue->capacity-(queue->front-queue->rear))%queue->capacity) == 1

И предложение

Во время постановки в очередь рекомендуется проверить, достигла ли очередь своей емкости или нет.