广度优先搜索期间的浮点异常

Question

其他一切似乎都工作正常，但 returns 在此图中执行 BFS 期间出现浮点异常。早些时候，该程序在调试期间运行良好，BFS 运行成功但在运行时崩溃。而现在，这也不再发生了。

不知道怎么回事。

代码：

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

//structure to define a node
struct node{
    int vertex;
    struct node *next;
};

//structure to define a graph
struct Graph{
    int numVertices;
    struct node** array;
};

//structure to define a queue
struct Q{
    int front, rear, size;
    int *array;
};

//create a node
struct node* createNode(int dest){
    struct node *new=(struct node*)malloc(sizeof(struct node));
    new->vertex=dest;
    new->next=NULL;
    return new;
}

//create a graph
struct Graph* createGraph(int num){
    struct Graph *graph=(struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices=num;
    graph->array=(struct node**)malloc(num*(sizeof(struct node*)));
    
    int i;
    for(i=0;i<num;i++)
        graph->array[i]=NULL;
    return graph;
}
//create a queue
struct Q* createQ(int size){
    struct Q *new=(struct Q*)malloc(sizeof(struct Q));
    new->front=new->rear=0;
    new->array=(int*)malloc(size*sizeof(int));
    return new;
}

//enqueue
void enqueue(struct Q *q,int data){
    if((q->rear+1)%q->size==q->front)
        printf("Queue is full.\n");
    else{
        q->rear=(q->rear+1)%q->size;
        q->array[q->rear]=data;
    }
}

//dequeue
int dequeue(struct Q *q){
    if(q->front==q->rear)
        printf("Queue is empty.\n");
    else{ 
        int x;
        q->front=(q->front+1)%q->size;
        x=q->array[q->front];
        return x;
    }
}

//is empty queue
int isEmpty(struct Q *q){
    if(q->front==q->rear)
        return 0;
    else return 1;
}

//BFS
void BFS(struct Graph *graph, int start){
    
    struct Q *q=createQ(graph->numVertices);
    struct node *temp;
    int curr;
    int *visited=(int*)malloc(graph->numVertices*sizeof(int));
    
    visited[start]=1;
    enqueue(q,start);
    
    while(!isEmpty(q)){
        curr=dequeue(q);
        printf("%d ",curr);
        
        temp=graph->array[curr];
        while(temp!=NULL){
            if(visited[temp->vertex]!=1){
                visited[temp->vertex]=1;
                enqueue(q,temp->vertex);
            }
            temp=temp->next;
        }
    }                
}

//add an edge to graph
void addEdge(struct Graph *graph,int src, int dest){
    
    //edge from src to dest
    struct node *new=createNode(dest);
    new->next=graph->array[src];
    graph->array[src]=new;
    
    //edge from dest to src
    new=createNode(src);
    new->next=graph->array[dest];
    graph->array[dest]=new;
    
}

//print a graph
void printGraph(struct Graph *graph){
    struct node *temp;
    int i;
    for(i=0;i<graph->numVertices;i++){
        temp=graph->array[i];
        printf("Adj List of Vertex %d",i);
        while(temp!=NULL){
            printf("-> %d",temp->vertex);
            temp=temp->next;
        }
        printf("\n");
    }
}

int main(){
    
    struct Graph *graph=createGraph(5);
    addEdge(graph, 0, 3); 
    addEdge(graph, 0, 4); 
    addEdge(graph, 1, 2); 
    addEdge(graph, 1, 3); 
    addEdge(graph, 1, 4); 
    addEdge(graph, 2, 3); 
    addEdge(graph, 3, 4); 
    
    printGraph(graph);
    
    BFS(graph,0);
}

Answer 1

您将在 enqueue 中获得 SIGFPE：

if ((q->rear + 1) % q->size == q->front)

这是因为 q->size 为零，您得到一个被零除异常。

q->size 从未设置正确。因此，在 createQ 中添加：

new->size = size;

广度优先搜索期间的浮点异常

Floating point exception during Breadth First Search

c

graph

breadth-first-search