编写第一题DFS和BFS的代码
时间: 2024-10-05 22:02:51 浏览: 19
对于第一题中要求编写的深度优先搜索(DFS)与广度优先搜索(BFS),下面是两个算法的基本伪代码实现框架,考虑到题目要求对邻接节点探索顺序进行不同尝试,这里给出了基础版本,并提示了如何调整以支持不同的节点访问顺序:
### 广度优先搜索(BFS)
```python
from collections import deque
def bfs(graph, start, end):
# 初始化队列用于存储待探索路径,以及一个集合用于记录已访问过的节点
queue = deque([[start]])
visited = set()
while queue:
# 取出并移除队首元素作为当前路径
path = queue.popleft()
current_node = path[-1]
# 如果到达目标节点,则返回路径
if current_node == end:
return path
# 标记为已访问
if current_node not in visited:
visited.add(current_node)
# 获取所有未访问邻居节点,并将这些节点添加到队尾
for neighbor in sorted(graph[current_node]): # 可通过调整sorted()内部逻辑来改变访问顺序
new_path = list(path)
new_path.append(neighbor)
queue.append(new_path)
return None # 没有找到从起点到终点的路径时返回None
```
### 深度优先搜索(DFS)
```python
def dfs(graph, start, end, path=[], visited=None):
if visited is None:
visited = []
# 将当前节点加入到路径列表及已访问列表
path = path + [start]
visited.append(start)
# 到达目标节点则返回路径
if start == end:
return path
# 对于每个相邻节点
for node in sorted(graph[start]): # 调整排序方式即可改变探索顺序
# 若该节点未被访问过,则递归调用dfs
if node not in visited:
result = dfs(graph, node, end, path, visited)
if result is not None:
return result
return None # 当前分支无解时回溯
```
注意:上述示例中的`graph`应该表示成字典形式,键是节点名称,值是由该节点指向的所有其他节点组成的列表或集合。此外,你可以通过修改`sorted()`函数内的逻辑或者直接替换它来控制节点访问的顺序,比如使用随机排序或其他自定义排序规则等方法。在实际编码过程中,请确保按照任务描述正确处理各种边界情况和异常输入。
阅读全文