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

无向图的最短路径可以使用广度优先遍历算法（BFS）来解决。

下面是C语言实现的无向图最短路径的BFS算法：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct {
    int adj[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int V, E; // 顶点数和边数
} Graph;

typedef struct {
    int vertex; // 顶点编号
    int depth; // 顶点所在层数
} Queue;

void createGraph(Graph *G) {
    int i, j, k, w;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->V, &G->E);
    for (i = 0; i < G->V; i++) {
        for (j = 0; j < G->V; j++) {
            G->adj[i][j] = 0;
        }
    }
    for (k = 0; k < G->E; k++) {
        printf("请输入第%d条边的起点、终点和权值：", k + 1);
        scanf("%d%d%d", &i, &j, &w);
        G->adj[i][j] = w;
        G->adj[j][i] = w;
    }
}

void BFS_shortest_path(Graph *G, int start, int end) {
    Queue q[MAX_VERTEX_NUM]; // 定义队列
    int visited[MAX_VERTEX_NUM] = {0}; // 定义已访问数组
    int front = 0, rear = 0; // 定义队首和队尾指针
    int i, j;
    q[rear].vertex = start; // 入队起点
    q[rear].depth = 0; // 起点所在层数为0
    rear++; // 队尾指针后移
    visited[start] = 1; // 起点已访问
    while (front < rear) { // 队列不为空
        Queue u = q[front]; // 取出队首元素u
        front++; // 队首指针后移
        if (u.vertex == end) { // 到达终点
            printf("从%d到%d的最短路径长度为%d\n", start, end, u.depth);
            return;
        }
        for (i = 0; i < G->V; i++) { // 遍历所有顶点
            if (G->adj[u.vertex][i] && !visited[i]) { // 与u相邻且未访问过
                q[rear].vertex = i; // 入队顶点i
                q[rear].depth = u.depth + 1; // i所在层数为u的层数加1
                rear++; // 队尾指针后移
                visited[i] = 1; // 标记i已访问
            }
        }
    }
    printf("从%d到%d不存在路径\n", start, end); // 未找到路径
}

int main() {
    Graph G;
    int start, end;
    createGraph(&G);
    printf("请输入起点和终点：");
    scanf("%d%d", &start, &end);
    BFS_shortest_path(&G, start, end);
    return 0;
}

其中，邻接矩阵`adj`表示图的连接情况，`visited`数组表示每个顶点是否已经被访问过，`Queue`结构体表示队列中的元素，包括顶点编号和所在层数。

`BFS_shortest_path`函数实现了BFS算法，其中使用队列来存储遍历的顶点。每次取出队首元素u，遍历u的所有相邻顶点i，如果i未被访问过，则将i入队，并标记为已访问。当遇到终点时，输出最短路径长度，否则输出不存在路径。