广度优先搜索 (BFS) 算法详解及数组实现

广度优先搜索 (BFS) 是一种用于遍历或搜索树或图的算法，它从根节点开始，逐层遍历节点，直到找到目标节点或遍历完整个图。在 BFS 中，我们使用队列来存储要遍历的节点。

以下是使用数组实现 BFS 算法的示例代码：

// 定义一个邻接矩阵表示图，graph[i][j]表示i和j之间是否有边
int graph[N][N];
// 定义一个数组来记录每个节点是否已经被访问过
bool visited[N];
// 定义一个队列来存储待遍历的节点
int q[N];

// BFS算法
void bfs(int start) {
    // 初始化visited数组
    memset(visited, false, sizeof(visited));
    // 将起始节点加入队列
    int front = 0, rear = 0;
    q[rear++] = start;
    visited[start] = true;
    // 开始遍历
    while (front < rear) {
        // 取出队列头部的节点
        int cur = q[front++];
        // 处理当前节点
        printf('%d ', cur);
        // 将当前节点的所有未访问过的邻居加入队列
        for (int i = 0; i < N; i++) {
            if (graph[cur][i] && !visited[i]) {
                visited[i] = true;
                q[rear++] = i;
            }
        }
    }
}

在以上代码中，我们使用邻接矩阵表示图，visited 数组记录每个节点是否已经被访问过，q 数组作为队列存储待遍历的节点。在 BFS 算法中，我们首先将起始节点加入队列并标记为已访问，然后逐个取出队列中的节点，处理它的邻居节点并将未访问过的邻居加入队列。重复这个过程直到队列为空。