在C中使用BSF算法找到最短路径

Question

我用C语言编写了使用BSF算法寻找最短路径的程序。 下面是代码

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

#define max 1000
int dist = 0;
int node, edge, INDEX, i, j;
    
struct queue {
    int *arr;
    int rear, front;
};

struct queue* createQueue() {
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));
    q->front = q->rear = -1;
    q->arr = (int*)malloc(max * sizeof(int));
    return q;
}

bool isEmpty(struct queue* q) {
    return (q->front == -1);
}

int pop(struct queue* q) {
    int item;
     if (isEmpty(q)) {
    //printf("Queue is empty");
    item = -1;
  } else {
    item = q->arr[q->front];
    q->front++;
    if (q->front > q->rear) {
      //printf("Resetting queue ");
      q->front = q->rear = -1;
    }
  }
    return item;
}

void push(struct queue* q, int add_item) {
    if (q->rear == max - 1)
        printf("queue Overflow \n");
    else {
        if (isEmpty(q))
            q->front = 0;
        q->rear = q->rear + 1;
        q->arr[q->rear] = add_item;
    }
}

struct node{
    int vertex;
    struct node* next;
}; 

struct node* createNode(int vertex){
    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

struct graph{
    int vertices;
    struct node** adjList;
    bool* visited;
    int* dist;
};

struct graph* createGraph(int vertices) {
    int i;
    struct graph* g = (struct graph*)malloc(sizeof(struct graph));
    g->vertices = vertices;
    g->adjList = (struct node**)malloc(vertices * sizeof(struct node*));
    g->visited = (bool*)malloc(vertices * sizeof(bool)); // Allocate memory for all vertices
    g->dist = (int*)malloc(vertices * sizeof(int));
    for (i = 0; i < vertices; i++) {
        g->adjList[i] = NULL;
        g->visited[i] = 0; // Initialize all vertices as not visited
        g->dist[i] = -1;
    }
    return g;
}

void addEdge(struct graph* g, int src, int dest){
    struct node* newNode = createNode(dest);
    newNode->next = g->adjList[src];
    g->adjList[src] = newNode;
    
    newNode = createNode(src);
    newNode->next = g->adjList[dest];
    g->adjList[dest] = newNode;
}

void printQueue(struct queue* q){
    int i;
    if (isEmpty(q)) {
    //printf("Queue is empty");
  } else {
    printf("\nQueue contains \n");
    for (i = q->front; i < q->rear + 1; i++) {
      printf("%d ", q->arr[i]);
    }
    printf("\n");
  }
}

int bfs(struct graph* g, int startVertex){
    struct queue* q = createQueue();
    
    g->visited[startVertex] = 1;
    push(q, startVertex);
    g->dist[startVertex] = 0;
    
    while(!isEmpty(q)){
        printQueue(q);
        int currentVertex = pop(q);
        if(currentVertex == INDEX){
            return g->dist[currentVertex];
        }
        printf("currentVertex = %d \n", currentVertex);
        struct node* temp = g->adjList[currentVertex];
        while(temp){
            int adjNode = temp->vertex;
            if(!g->visited[adjNode]){
                g->visited[adjNode] = 1;
                g->dist[adjNode] = g->dist[currentVertex] + 1;
                push(q, adjNode);
            }
            temp=temp->next;
        }
    }
    return -1;
}

int main(){
    scanf("%d %d %d", &node, &edge, &INDEX);
    struct graph* g = createGraph(node);
    
    for(i=0; i<edge; i++){
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(g, src, dest);
    }
    
    printf("shortest distance = %d", bfs(g, 4));
    
    return 0;
}

如果起始节点为1和2，代码可以正常工作，但是当起始节点为3、4或5时，操作将终止，主函数将返回3221225477。 当起始节点为 3 时，输出如下所示。

5 7 2
1 2
2 1
2 2
3 2
2 5
5 3
4 5
currentVertex = 3
currentVertex = 5

--------------------------------
Process exited after 9.651 seconds with return value 3221225477
Press any key to continue . . .

不确定代码有什么问题，chatgpt 的建议没有帮助。我知道 c 可能不是解决这个问题的好语言，但这只是出于学习目的，希望可以在这里找到答案，否则我将不得不放弃使用 c。

Answer 1

问题是您没有在图结构中为顶点 5 分配条目（在示例中）。更深层次的原因是输入通过 1 到 𝑛 之间的数字指定节点，而不是 0 到 𝑛−1 之间的数字。这意味着您的算法会将值分配给

g->adjList[5]

、

g->visited[5]

、

g->dist[5]

，它们都在分配的内存之外。

快速解决方案是更改传递给

createGraph

的参数：

    struct graph* g = createGraph(node+1);