当前位置： 面试刷题>> 图的广度优先搜索(经典算法150题)
### 题目描述补充
**题目：图的广度优先搜索（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
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 示例代码
```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 示例代码
```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`集合（或数组）来记录已访问的节点，从而避免重复访问。