广度优先搜索的代码实现python
时间: 2023-11-05 11:05:28 浏览: 39
广度优先搜索(BFS)是一种图遍历算法,它从起始节点开始,逐层扩展,直到找到目标节点或遍历完整个图。下面是广度优先搜索的代码实现示例(以邻接表形式表示图):
```python
from collections import deque
def bfs(graph, start, target):
visited = set() # 记录已访问过的节点
queue = deque([(start, [])]) # 使用队列来辅助遍历,同时记录路径
while queue:
node, path = queue.popleft()
if node == target:
return path + [node] # 找到目标节点,返回路径
if node not in visited:
visited.add(node)
queue.extend((neighbor, path + [node]) for neighbor in graph[node])
return None # 目标节点不可达
# 示例使用:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
start_node = 'A'
target_node = 'F'
path = bfs(graph, start_node, target_node)
if path:
print(f"从节点 {start_node} 到节点 {target_node} 的路径为: {' -> '.join(path)}")
else:
print(f"从节点 {start_node} 到节点 {target_node} 不可达")
```