一、深度优先搜索算法介绍

深度优先搜索算法（Depth-First-Search）的基本思想是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。算法步骤如下：

1.访问顶点v；

2.依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；

3.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

二、部分代码

import mathimport matplotlib.pyplot as pltshow_animation = Trueclass DepthFirstSearchPlanner:def __init__(self, ox, oy, reso, rr):"""Initialize grid map for Depth-First planningox: x position list of Obstacles [m]oy: y position list of Obstacles [m]resolution: grid resolution [m]rr: robot radius[m]"""self.reso = resoself.rr = rrself.calc_obstacle_map(ox, oy)self.motion = self.get_motion_model()class Node:def __init__(self, x, y, cost, parent_index, parent):self.x = x  # index of gridself.y = y  # index of gridself.cost = costself.parent_index = parent_indexself.parent = parentdef __str__(self):return str(self.x) + "," + str(self.y) + "," + str(self.cost) + "," + str(self.parent_index)

三、部分结果

四、完整Python代码

见下方联系方式