深度优先搜索（DFS）和广度优先搜索（BFS）两种算法c++

1、BFS和DFS介绍

���度优先搜索(DFS)和广度优先搜索(BFS)是一种用于遍历或搜索树图的一种算法，在这个过程中保证图或数的每个结点被访问且仅被访问一次，再按照每个结点访问的顺序不同分为深搜和广搜。

本文只讨论这两种算法在搜索方面的应用！

1.1深度优先搜索算法

深度优先搜索(Depth-First-Search，DFS)它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

这个算法可以用递归实现也可以用栈实现。使用递归很容易理解而且代码量较少，当然它也有缺点，就是对规模较大的图或数使用递归思路会导致栈溢出。目前阶段我都会使用递归去实现深搜。

1.2广度优先搜索算法

广度优先搜索（Breadth-First-Search，BFS）这个算法很好理解，直观的解释它就像一个炸弹爆炸时那种层层推进的搜索方式，是要当前结点周围的结点符合搜索条件，那么就同步地将当前结点周围的结点作为源节点继续宽搜，直到找到目标结点为止。

这个算法独特的搜索策略就决定了它的最终搜索结果一定是最优解！所以目前只要我看到有最优解要求时，我会毫不犹豫的选择BFS。

1、BFS和DFS的经典应用

 起初我认为DFS只有在特定的情况的情况才有最优解，但是if语句确实万能，通过对这个语句的灵活运用，DFS依旧可以实现最优解（虽然意义不大。因为BFS的实现更简单，而且时间复杂度更低！）。

1.1迷宫问题应用

1.1.1原始版

问题描述：现给出一个30*50的迷宫矩阵（见代码），其中标记1为障碍物，0为可以通行的地方。迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。

请注意在字典序中 D