c - C中使用队列的BFS遍历程序
问题描述
我目前正在研究图形,并且正在使用 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));
}
解决方案
正如人们指出的那样,您的 bfs 工作正常,您的队列 isEmpty() 函数存在缺陷。它应该检查2个条件,
到目前为止,还没有元素入队或出队。为此,条件是
(queue->front==-1 && queue->rear==-1)
所有入队的元素都已出队,例如,在队列中,您已入队 2 、 3 ,然后后面 = 0 和前面 = 1。现在您已将 2 个元素出队,这使队列为空,并且后部 = 2 和前部 = 1。这是后部超过前部的情况。您必须检查前索引和后索引之间的差异等于 1 的条件。
((queue->capacity-(queue->front-queue->rear))%queue->capacity) == 1
和一个建议
在排队时,最好检查队列是否已经达到其容量。
推荐阅读
- c++ - MSVC2013:如何避免使用错误的预构建脚本中止构建过程(错误 MSB3073: :VCEnd" 退出,代码 -1)
- python - 如果列表包含大小不相等的元组,如何迭代?
- immutable.js - 将 immutable.js 对象传递给 Ramda 函数不起作用 - 不调用管道函数
- python - 使用熊猫在csv中通过另一列中的条件更新一列中的值
- javascript - Webpack:将 svg 文件加入符号并为每个条目生成 css (sass) 样式表
- ios - 在 cellForRowAt 中手动触发 didSelectRowAtIndexPath 会导致实际 didSelectRowAtIndexPath 委托方法中的单元格为零
- git - 如何在 Visual Studio 中为所有子模块创建新分支
- git - 如何识别 git hook 脚本是否真的作为钩子运行
- php - Laravel 5.6 在我的刀片视图中显示 svg 图标不起作用
- php - 如何使删除按钮仅在表格的最后一行显示和执行操作?