1,BFS
可以求解最短路径等 最优解 问题
BFS 先进先出
在程序实现 BFS 时需要考虑以下问题:
队列:用来存储每一轮遍历得到的节点;
标记:对于遍历过的节点,应该将它标记,防止重复遍历
path = [[0,0]] ##头结点放入
while path:
for _ in range(len(path)): 遍历每一层节点
for new_x, new_y in [[x - 1, y - 1], [x - 1, y], [x - 1, y + 1], [x, y - 1],
[x, y + 1], [x + 1, y - 1], [x + 1, y], [x + 1, y + 1]]: #几个方向的遍历
各种边界条件的判断
将新的节点加path
2,DFS
在程序实现 DFS 时需要考虑以下问题:
栈:用栈来保存当前节点信息,当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
标记:和 BFS 一样同样需要对已经遍历过的节点进行标记。
先进后出
带数组的版本
不带数组,用递归代替