C语言BFS算法实现无向图最短路径

在C语言中，广度优先搜索(Breadth First Search，简称BFS)是一种用于查找图中两个顶点之间最短路径的经典算法。对于无向图来说，BFS可以找到从起点到所有其他节点的最短路径。以下是基本的BFS算法实现步骤：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100 // 图的最大顶点数

// 定义邻接矩阵表示的图结构
typedef struct {
    int adj_matrix[MAX_VERTICES][MAX_VERTICES];
    bool visited[MAX_VERTICES]; // 记录每个节点是否已访问过
} Graph;

void bfs(Graph *graph, int start) {
    int i, j;
    bool *queue = (bool *)malloc(sizeof(bool) * MAX_VERTICES); // 队列存储节点状态
    for (i = 0; i < MAX_VERTICES; i++) {
        queue[i] = false;
        graph->visited[i] = false;
    }
    
    queue[start] = true; // 将起始节点放入队列
    graph->visited[start] = true;
    
    while (!queue[0]) { // 当队列非空时继续
        for (i = 0; i < MAX_VERTICES; i++) {
            if (queue[i] && !graph->visited[i]) {
                printf("%d ", i); // 输出当前节点
                for (j = 0; j < MAX_VERTICES; j++) {
                    if (graph->adj_matrix[i][j] == 1) { // 如果有边相连
                        graph->visited[j] = true; // 标记邻居节点已访问
                        queue[j] = true; // 放入队列
                    }
                }
            }
        }
        
        queue[start] = false; // 移除已经处理过的起始节点
    }
    free(queue);
}

int main() {
    Graph g;
    // 初始化邻接矩阵...
    // 调用bfs函数传入图和起始节点
    bfs(&g, 0);
    return 0;
}