简介：
1.DFS（深度优先搜索）算法是一种用于遍历或搜索树或图数据结构的算法。该算法从起始顶点开始，沿着一条路径尽可能深入地访问顶点，直到该路径上的所有顶点都被访问过为止。然后回溯到前一个顶点，继续探索其他路径，直到所有可能的路径都被探索完毕。（不撞南墙不回头）
2.BFS（广度优先搜索）算法是一种用于遍历或搜索树或图数据结构的算法。与DFS不同，BFS从起始顶点开始，先访问起始顶点的所有相邻顶点，然后再依次访问这些相邻顶点的相邻顶点，依此类推，直到所有顶点都被访问过为止。
实现：
1.DFS算法通常使用递归或栈来实现。在递归实现中，每次访问一个顶点时，递归地访问其相邻的未访问过的顶点。在栈实现中，将起始顶点入栈，然后循环弹出栈顶顶点并访问其相邻的未访问过的顶点，将这些相邻顶点入栈，直到栈为空。
2.BFS算法通常使用队列来实现。将起始顶点入队，然后循环从队列中取出顶点并访问其相邻的未访问过的顶点，将这些相邻顶点入队，直到队列为空。
实例：
谈起DFS和BFS，在算法篇中最出名的就是迷宫问题了吧。给定一个由数字0和1组成的矩阵，我们将其称之为迷宫，数字1代表墙壁，0则代表着可以正常走的路。要求我们找到一条可以从起点到达终点的路线并将其输出。
这时候就需要引入我们的搜索算法DFS和BFS，这两种算法对不同的题目要求有不同的优势。比如DFS可以更加迅速的找到出路，找到出路即停止寻找。但是不能保证这条路是最优路线（即不能保证路程最短）；而BFS可以遍历所有可能的路线并找到其中的 最优解（即路程最短的路线），但是BFS需要遍历所有可能的路线，而且需要更多的空间去储存队列，所以其复杂度会略高于DFS。下面直接上迷宫：
maze=[ [1,1,1,1,1,1,1,1,1,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,0,0,1,1,0,0,1], [1,0,1,1,1,0,0,0,0,1], [1,0,0,0,1,0,0,0,0,1], [1,0,1,0,0,0,1,0,0,1], [1,0,1,1,1,0,1,1,0,1], [1,1,0,0,0,0,0,0,0,1], [1,1,1,1,1,1,1,1,1,1] ] # 起点为(1,1);终点为(8,8) dirs=[ lambda x,y:(x+1,y), #往右走 lambda x,y:(x-1,y), #往左走 lambda x,y:(x,y+1), #往下走 lambda x,y:(x,y-1) #往上走 ]
如果我们仅仅需要找到行得通的路线的话，我们可以使用DFS来解决，下面附上DFS的解题代码：
# DFS 解法 def maze_path(x1,y1,x2,y2): stick=[(x1,y1)] while stick: curcode=stick[-1] # 后进先出 if curcode[0]==x2 and curcode[1]==y2: # 到达终点的判断 for j in stick: print(j) print(len(stick)) # 一共走的步数 return True for dir in dirs: # 四条路遍历 nextcode=dir(curcode[0],curcode[1]) # 对x,y进行改变的一个过程 if maze[nextcode[0]][nextcode[1]] == 0: # 能走 stick.append((nextcode)) maze[nextcode[0]][nextcode[1]]=2 # 代表走过了 break # 有一条路能走时，就立即break，保证只走一条路，一条路走到黑。这就是DFS的魅力！ else: maze[nextcode[0]][nextcode[1]] = 2 #四条路都不能走 stick.pop() # 删掉这个节点，退一步，继续找出路。 else: print('没有路') return False maze_path(1,1,8,8)
然而，在实际问题中，我们往往需要找到最优解，而DFS则无法实现此功能，此时我们运用BFS广度优先来解决。下面附上BFS解题代码：
# BFS 解法 from collections import deque def print_r(path): # 输出函数，定义了输出的格式 curnode=path[-1] realpath=[] while curnode[2]!=-1: realpath.append(curnode[0:2]) curnode= path[curnode[2]] realpath.append(curnode[0:2]) # 起点 realpath.reverse() for i in realpath: print(i) def maze_path_queue(x1,y1,x2,y2): queue = deque() # 运用了队列 queue.append((x1,y1,-1)) # 最大的不同就是 这里多了一个下标 用于储存子父关系 方便后续的输出 path=[] while queue: curnode=queue.popleft() # 先进先出 path.append(curnode) if curnode[0]==x2 and curnode[1]==y2: # 到达终点的判断 # 终点 print_r(path) # 调用输出函数 return True for dir in dirs: nextnode = dir(curnode[0],curnode[1]) # 调用dir中的lambda函数，对x,y进行修改 if maze[nextnode[0]][nextnode[1]] ==0: # 表示能走 queue.append((nextnode[0],nextnode[1],len(path)-1)) maze[nextnode[0]][nextnode[1]]=2 # 标记为已经走过 这里没有用break 因为是广度优先 所有情况都要遍历一遍 不过这里的子父关系很明确 else: print('没有路') return False maze_path_queue(1,1,8,8)
比较：
两者相比较，不难看出BFS要略比DFS复杂一些，在BFS中我们引入了队列并额外定义了一个输出函数print_r,以满足我们的格式要求并计算出最短路径的步数。
说明：
迷宫问题是数据结构与算法DFS+BFS篇中比较典型且综合的题目，通过此类问题可以提高我们的代码实现能力，帮助我们掌握DFS以及BFS算法基础。对于稍有难度且重要的知识点我们要多多回顾并总结。
温故而知新，可以为师矣！
