用Python或者c语言 写广度优先和深度优先搜索
时间: 2023-01-11 19:55:36 浏览: 133
广度优先搜索程序c语言编写
4星 · 用户满意度95%
好的,我将用 Python 为你示例如何实现广度优先搜索和深度优先搜索。
广度优先搜索(BFS)是一种图的搜索算法,它的目标是从源点开始,找到一条最短的路径到目标点。
算法流程:
1. 将源点加入队列。
2. 从队列中取出队首结点。
3. 将队首结点的所有相邻结点加入队列。
4. 将队首结点标记为已访问。
5. 重复步骤 2-4,直到队列为空。
Python 实现如下:
```
# 定义图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
def bfs(graph, start, end):
# 创建一个队列,用于存储需要访问的结点
queue = []
# 将源点加入队列
queue.append(start)
# 创建一个集合,用于存储已访问的结点
visited = set()
# 循环遍历队列
while queue:
# 从队列中取出队首结点
node = queue.pop(0)
# 判断是否到达目标点
if node == end:
return True
# 将队首结点的所有相邻结点加入队列
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
# 未找
阅读全文