使用c语言中的广度优先便利实现求出无向图的最短距离

这里提供一个基于邻接矩阵表示无向图的广度优先搜索算法，可以求出起点到其他所有点的最短距离（如果存在路径的话）。

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

#define MAX_N 100 // 最大顶点数
#define INF 0x3f3f3f3f // 无穷大值

int n; // 顶点数
int graph[MAX_N][MAX_N]; // 邻接矩阵
int dist[MAX_N]; // 起点到各个顶点的最短距离
bool visited[MAX_N]; // 标记是否已访问

// 广度优先遍历
void bfs(int start) {
    // 初始化距离和标记
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[start] = 0; // 起点到自身距离为0

    // 遍历队列
    int queue[MAX_N];
    int front = 0, rear = 0;
    queue[rear++] = start;
    visited[start] = true;

    while (front < rear) {
        int curr = queue[front++]; // 出队
        for (int i = 0; i < n; i++) {
            if (graph[curr][i] > 0 && !visited[i]) { // 连通且未访问
                dist[i] = dist[curr] + 1; // 更新距离
                visited[i] = true; // 标记已访问
                queue[rear++] = i; // 入队
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    // 输入邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    int start;
    printf("请输入起点编号：");
    scanf("%d", &start);

    bfs(start);

    // 输出最短距离
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) {
            printf("起点%d到顶点%d无法到达\n", start, i);
        } else {
            printf("起点%d到顶点%d的最短距离为%d\n", start, i, dist[i]);
        }
    }

    return 0;
}

该算法的时间复杂度为 $O(n^2)$，其中 $n$ 是顶点数，因为需要遍历邻接矩阵中的所有元素。如果使用邻接表表示图，时间复杂度可以优化到 $O(n+m)$，其中 $m$ 是边数。