2.5　用深度优先搜索在迷宫中找到出路

深度优先搜索（DFS）算法是一个适合小内存设备的寻路算法，另一种常见用法是构建迷宫，只对访问和发现的节点列表做一些修改，然而主要的算法还是一样的。

准备工作

DFS是一个上层算法，依赖于图的每个主要函数的实现（build, init等），所以这个算法在Graph类中实现。

请花点时间验证一下该方法在什么时候操作实际的游戏对象或者顶点ID。

操作步骤

虽然本节只定义一个函数，但是请注意代码中的注释，以便更好地理解代码逻辑：

1. 声明GetPathDFS函数：

2. 验证输入对象是否为null：

3. 声明并初始化算法需要用到的变量：

4. 实现用于查找路径的DFS算法：

运行原理

此算法基于DFS的迭代版本，也基于图的顺序遍历和使用栈遍历节点并添加发现的节点的后进先出原则。

延伸阅读

我们调用了BuildPath函数，但是并没有实现它，请注意这个函数几乎在本章中的每个寻路算法中都被调用，这也是为什么它不是本方法的一部分。

下面是BuildPath的代码：