目录1 )前言)广度优先搜索和深度优先搜索)深度优先搜索)深度优先搜索算法框架1 )二叉树深度优先搜索模板2 )图深度优先搜索模板3 )二维矩阵深度优先搜索模板4 )广度优先搜索算法框架1 )
1 .前言深度优先搜索算法的基础是递归。 如果你对递归还不熟悉，我建议你先去看递归的概念。 请做递归练习题，也读一下我先写的递归文章。 递归算法详细信息
2 .广度优先搜索和深度优先搜索是本文同时总结广度优先搜索和深度优先搜索的，为这两种算法是针对 “图” 的遍历方法。 当然这里的图是指广义图，可以是实际图，也可以是n叉树，也可以是二维矩阵。 其中在http://www.Sina.com/http://www.Sina.com /二叉树的遍历过程中说明两种搜索算法的差异。
1 )深度优先搜索这种搜索方法是单向穷举搜索，首先继续搜索左子树直到某个节点没有左子树，然后改变方向搜索右子树。 图如下。
2 )宽度优先搜索与深度搜索的不同之处在于，该搜索方式总是沿着层次进行，由于是当前层次，所以节点都被访问后向下进行。 图如下所示。
3 .访问深度优先搜索算法框架void DFS (当前节点)； 在此插入代码片段`标记当前节点已访问； for (下一个节点：当前节点的相邻列表)剪枝(如果下一个节点已经访问，则跳过)； DFS (下一个节点； }1)二叉树深度优先搜索模板//二叉树顺序DFS搜索voidDFS(treenode*root ) if ) root==nullptr ) return； cout root-val '； //输出当前节点//此处不需要将当前节点标记为已访问。 因为二叉树不会返回根液晶(DFS )。 根循环(DFS )； }调整输出节点的位置还可以获得其他两种类型的二叉树DFS遍历。
//二叉树中序DFS搜索voidDFS(treenode*root ) if ) root==nullptr ) return； 根液晶屏(DFS )； cout root-val '； //输出当前节点DFS (根链路)； (//二叉树后的DFS搜索voidDFS(treenode*root ) if ) root==nullptr ) return； 根液晶屏(DFS )； 根循环(DFS )； cout root-val '； //输出当前节点} 2)图深度优先搜索模板vectorint visited； //输出用于标记访问的节点voidDFS(graph*g，int v ) { cout v ' )的//当前节点visited[v]=1将当前节点标记为已访问的for (例如w G-vexnum； w () if (！ 可视[ w ] ) DFS(g，w )； }3)二维矩阵深度优先搜索模板int m=matrix.size (； //行数int n=matrix[0].size (； //列数vectorvectorint (未授权(m，vectorint ) n，0 )； //已访问的节点int directions [4] [2]={-1，0 }、{ 1，0 }、{0，-1}、{ 0，1 }； //行进方向void DFS (向量矩阵，int x，int y ) ) if )矩阵[ x ] [ y ]==target ) return； 可视[ x ] [ y ]=1； //将当前节点标记为已访问的for (inti=0； i 4； I ) { int new_x=x directions[i][0]； int new_y=y directions[i][1]； //在此请务必将visites[new_x][new_y]放在最后。 因为计算后的new_x和new_y的值可能超过了vis
ited的下标访问范围 if(new_x < 0 || new_x >= m || new_y < 0 || new_y >= n || visited[new_x][new_y]) continue; DFS(matrix, new_x, new_y); }}4. 广度优先搜索算法框架
首先需要明确的就是，广度优先搜索是按照层次遍历的，所以广度优先搜索不能像深度优先搜索一样使用递归来实现，广度优先搜索需要申请辅助队列来记录下一层需要遍历的节点
1）单源广度优先搜索从一个起点出发到一个终点结束
//单源的广度优先搜索int BFS(elemType start, elemType target) { queue<elemType> q; //申请辅助队列 set<elemType> visited; //标记已访问过的，避免走回头路 q.push(start); //起点入队列 visited.insert(start); //标记起点 int step = 0; //记录步数 while (!q.empty()) { int sz = q.size(); //每一层的元素个数 for (int i = 0; i < sz; i++) { elemType cur = q.pop(); //获得队列中的元素 if (cur == target) { //判断是否需要结束搜索 return step; } for (elemType x : cur.neighbor()) { //确定下一层需要搜索的节点 if (visited.find(x) == visited.end()) { q.push(x); visited.insert(x); } } } step++; // 步数加一 }} 2）多源广度优先搜索 健康的板栗，多源广度优先搜索的意思是可以从多个起点开始向外进行搜索，是一种扩散式的搜索方法，如下图所示，图中值为0的点表示起点，则与每个0上下左右相邻的节点值就为1，同样与每个1上下左右相邻的节点值就为2。
[注]：上述的两种广度优先搜索中我们给出了两个记录步长的方式，第一种是设置一个step，然后每向前一步就step++，这种比较适合单源的广度优先搜索；第二种是设置一个辅助dist数组，记录所有节点的距离，然后通过 dist[newNode] = dist[oldNode]+1 进行更新，这种比较适合多源的广度优先搜索。
3）双向广度优先搜索 广度优先搜索是求图中最短路径的方法，一般是从某个起点出发，一直穷举直到碰到某个结束值(也就是目标值)，这样的搜索过程就是单向的搜索，而有的题目即会提供起点位置，也会提供终点的位置，这样的题目可以采用双向的广度优先搜索， 当发现某一时刻两边都访问过同一顶点时就停止搜索。比如下面这个题目：
LeetCode 127. 单词接龙：在本题目中起始单词 beginword 和 结束单词 endword均已经给出，因此可以采用双向的广度优先搜索。
双向广度优先搜索算法流程：
1. 需要定义两个辅助队列，一个放前向搜索时的节点，一个存放逆向搜索时的节点
2. 查看两个辅助队列中是否有相同的元素，以判断搜索是否结束
3. 轮流进行搜索，也就是前向搜索进行一次后紧跟着就要做一次逆向搜索