c语言使用广度优先遍历求无向图的最短路径

广度优先遍历可以用来求无向图的最短路径，具体实现可以参考以下代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100

typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

int isEmpty(Queue* q) {
    return q->front == -1 && q->rear == -1;
}

void enQueue(Queue* q, int x) {
    if ((q->rear+1) % MAX_QUEUE_SIZE == q->front) {
        printf("Queue is full.\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
        q->rear = 0;
    } else {
        q->rear = (q->rear+1) % MAX_QUEUE_SIZE;
    }
    q->data[q->rear] = x;
}

void deQueue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }
    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        q->front = (q->front+1) % MAX_QUEUE_SIZE;
    }
}

int getFront(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }
    return q->data[q->front];
}

void BFS(int** graph, int* visited, int n, int start, int end) {
    Queue q;
    initQueue(&q);
    enQueue(&q, start);
    visited[start] = 1;
    while (!isEmpty(&q)) {
        int curr = getFront(&q);
        printf("%d ", curr);
        deQueue(&q);
        if (curr == end) {
            printf("\nFound shortest path.\n");
            break;
        }
        for (int i = 0; i < n; i++) {
            if (graph[curr][i] && !visited[i]) {
                enQueue(&q, i);
                visited[i] = 1;
            }
        }
    }
}

int main() {
    int n = 5;
    int start = 0;
    int end = 4;
    int** graph = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        graph[i] = (int*)calloc(n, sizeof(int));
    }
    graph[0][1] = 1;
    graph[0][2] = 1;
    graph[1][3] = 1;
    graph[2][3] = 1;
    graph[3][4] = 1;
    int* visited = (int*)calloc(n, sizeof(int));
    printf("BFS traversal: ");
    BFS(graph, visited, n, start, end);
    free(visited);
    for (int i = 0; i < n; i++) {
        free(graph[i]);
    }
    free(graph);
    return 0;
}

这里使用了一个队列来辅助进行广度优先遍历，visited数组用来记录每个节点是否被访问过。在遍历过程中，如果遇到终点节点就找到了最短路径，可以退出循环。