C语言实现图的广度优先遍历

广度优先遍历（BFS）是一种基于队列实现的图遍历算法，它从起点开始，依次访问与当前节点相邻的所有未访问过的节点，直到所有可达节点都被访问。下面是使用C语言实现图的广度优先遍历的示例代码：

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

#define MAX_VERTEX_NUM 100 // 最大节点数量

typedef struct {
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 图的邻接矩阵
    int vertexNum; // 节点数量
} Graph;

void initGraph(Graph *graph) {
    int i, j;
    graph->vertexNum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        for (j = 0; j < MAX_VERTEX_NUM; j++) {
            graph->edges[i][j] = 0;
        }
    }
}

void addEdge(Graph *graph, int from, int to) {
    graph->edges[from][to] = 1; // 添加一条边
    graph->edges[to][from] = 1; // 无向图需要添加反向边
}

void BFS(Graph *graph, int start) {
    int visited[MAX_VERTEX_NUM]; // 用来记录节点是否已经被访问
    int queue[MAX_VERTEX_NUM]; // 队列
    int front = 0, rear = 0; // 队首和队尾指针
    int i, j;

    for (i = 0; i < graph->vertexNum; i++) {
        visited[i] = 0;
    }

    visited[start] = 1; // 标记起点已经被访问
    queue[rear++] = start; // 将起点入队

    while (front != rear) { // 队列不为空时循环
        int curr = queue[front++]; // 取出队首节点
        printf("%d ", curr); // 访问节点

        for (j = 0; j < graph->vertexNum; j++) {
            if (graph->edges[curr][j] && !visited[j]) { // 如果当前节点有相邻节点未被访问
                visited[j] = 1; // 标记该节点已经被访问
                queue[rear++] = j; // 将该节点入队
            }
        }
    }
}

int main() {
    Graph graph;
    initGraph(&graph);
    graph.vertexNum = 8;
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 0, 3);
    addEdge(&graph, 1, 4);
    addEdge(&graph, 1, 5);
    addEdge(&graph, 2, 6);
    addEdge(&graph, 2, 7);
    BFS(&graph, 0); // 从0节点开始遍历
    return 0;
}

以上代码中，`Graph`结构体表示一个无向图，其中`edges`数组是表示图的邻接矩阵，`vertexNum`表示节点数量。`initGraph`函数用于初始化图，将所有节点的邻接矩阵设为0。`addEdge`函数用于添加边，参数`from`和`to`表示边的起点和终点。`BFS`函数是广度优先遍历算法的具体实现，参数`start`表示从哪个节点开始遍历。在函数中，我们使用了一个`visited`数组来记录每个节点是否已经被访问过，使用一个队列来存储待访问节点。首先将起点入队，并将其标记为已访问。然后进入循环，每次从队列中取出队首节点，并访问该节点，同时将与该节点相邻的未访问过的节点入队，并标记为已访问。当队列为空时，遍历结束。在主函数中，我们创建一个图，并添加一些边，并从节点0开始进行广度优先遍历。