题目描述补充

题目：图的广度优先搜索（Breadth-First Search, BFS）

给定一个无向图（或有向图）的邻接表表示，实现图的广度优先搜索算法。广度优先搜索算法从一个选定的源节点开始，探索所有邻近的节点，然后逐层向外扩展，直到访问完图中所有可达的节点。在搜索过程中，需要记录访问过的节点以避免重复访问。

输入：

1. 图的表示（这里以邻接表为例）。
2. 源节点。

输出：

• 访问节点的顺序（即BFS遍历的顺序）。

示例

假设我们有如下的无向图，用邻接表表示：

Graph:
0 ---- 1
|      |
|      |
v      v
2 ---- 3

邻接表可以表示为：

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

若源节点为0，则BFS遍历的顺序应为 [0, 1, 2, 3]。

PHP 示例代码

<?php
function bfs($graph, $start) {
    $visited = array_fill_keys(array_keys($graph), false); // 初始化访问数组
    $queue = new SplQueue(); // 使用队列进行BFS
    $queue->enqueue($start); // 将起始节点加入队列
    $visited[$start] = true; // 标记起始节点为已访问
    $result = [];

    while (!$queue->isEmpty()) {
        $current = $queue->dequeue(); // 出队
        $result[] = $current; // 添加到结果中

        foreach ($graph[$current] as $neighbor) {
            if (!$visited[$neighbor]) {
                $queue->enqueue($neighbor); // 将未访问的邻居节点加入队列
                $visited[$neighbor] = true; // 标记为已访问
            }
        }
    }

    return $result;
}

// 示例图
$graph = [
    0 => [1, 2],
    1 => [0, 3],
    2 => [0, 3],
    3 => [1, 2]
];

// 调用BFS函数
$start = 0;
$result = bfs($graph, $start);
print_r($result);
?>

Python 示例代码

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []

    while queue:
        current = queue.popleft()
        result.append(current)

        for neighbor in graph[current]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

    return result

# 示例图
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

# 调用BFS函数
start = 0
result = bfs(graph, start)
print(result)

JavaScript 示例代码

function bfs(graph, start) {
    const visited = new Set();
    const queue = [start];
    const result = [];

    visited.add(start);

    while (queue.length > 0) {
        const current = queue.shift();
        result.push(current);

        for (const neighbor of graph[current]) {
            if (!visited.has(neighbor)) {
                queue.push(neighbor);
                visited.add(neighbor);
            }
        }
    }

    return result;
}

// 示例图
const graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
};

// 调用BFS函数
const start = 0;
const result = bfs(graph, start);
console.log(result);

在这些示例中，我们使用了队列来存储待访问的节点，并借助visited集合（或数组）来记录已访问的节点，从而避免重复访问。