简述深度优先搜索遍历的方法。

简述深度优先搜索遍历的方法？深度优先搜索算法(Depth-First-Search, DFS)，最初是一种用于遍历或搜索树和图的算法，在LeetCode中很常见，虽然感觉不难，但是理解起来还是有点难度的。

简要概括，深度优先的主要思想就是“不撞南墙不回头”，“一条路走到黑”，如果遇到“墙”或者“无路可走”时再去走下一条路。

思路

假如对树进行遍历，沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当达到边际时回溯上一个节点再进行搜索。如下图的一个二叉树。



首先给出这个二叉树的深度优先遍历的结果(假定先走左子树)：1-2-4-5-3-6-7

那是怎样得到这样的结果呢？

根据深度优先遍历的概念：沿着这树的某一分支向下遍历到不能再深入为止，之后进行回溯再选定新的分支。

定义节点

class TreeNode{

int val;

TreeNode left;

TreeNode right;

}

递归的方式

分别对左右子树进行递归，一直到底才进行回溯。如果不了解递归可以参考我的博客你真的懂递归吗？。

class Solution{

public void depthOrderTraversalWithRecusive(TreeNode root){

if(root == null){

return;

}

System.out.print(root.val +"-");

depthOrderTraversalWithRecusive(root.left);

depthOrderTraversalWithRecusive(root.right);

}

}

迭代的方式

上面实现了递归方式的深度优先遍历，也可以利用栈把递归转换为迭代的方式。

但是为了保证出栈的顺序，需要先压入右节点，再压左节点。

class Solution{

public void depthOrderTraversalWithoutRecusive(TreeNode root){

if(root == null) return;

StackTreeNode stack = new Stack();

stack.push(root);

while(!stack.isEmpty()){

TreeNode node = stack.pop();

System.out.print(node.val + "-");

if(node.right != null){

stack.push(node.right);

}

if(node.left != null){

stack.push(node.left);

}

}

}

}

接着再列举个利用深度优先遍历的方式的题目

扫雷

给定一个表示游戏板的二维字符矩阵，'M'表示一个未挖出的地雷，'E'表示一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。

根据以下规则，返回相应位置被点击后对应的面板：

如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为'X'。

如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的方块都应该被递归地揭露。

如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。

如果在此次点击中，若无更多方块可被揭露，则返回面板。

示例

输入:

[['E', 'E', 'E', 'E', 'E'],

['E', 'E', 'M', 'E', 'E'],

['E', 'E', 'E', 'E', 'E'],

['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

输出:

[['B', '1', 'E', '1', 'B'],

['B', '1', 'M', '1', 'B'],

['B', '1', '1', '1', 'B'],

['B', 'B', 'B', 'B', 'B']]

思路：根据给定的规则，当给定一个Click坐标，当不为雷的时候以此坐标为基点向四周8个方向进行深度遍历，把空格E填充为B，并且把与地雷M相连的空方块标记相邻地雷的数量。

注意 ：



在这个题中可以沿着8个方向递归遍历，所有要注意程序中，采用了两个for循环可以实现向8个方向递归。

深度优先搜索法和广度优先搜索法

深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的结点，如果它还有以此为起点而未搜过的边，就沿着边继续搜索下去。当结点v的所有边都已被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个过程反复进行直到所有结点都被发现为止。

深度优先搜索基本算法如下{递归算法}：

PROCEDURE dfs_try(i);

FOR i:=1 to maxr DO

BEGIN

IF 子结点 mr 符合条件 THEN

BEGIN

产生的子结点mr入栈；

IF 子结点mr是目标结点

THEN 输出

ELSE dfs_try(i+1);

栈顶元素出栈;

END;

END; 宽度优先搜索算法（又称广度优先搜索算法）是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta单源最短路径算法和Prim最小生成树算法都采用了与宽度优先搜索类似的思想。

宽度优先搜索的核心思想是：从初始结点开始，应用算符生成***层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有***层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点……，如此依次扩展，直到发现目标结点为止。

宽度优先搜索基本算法如下：

list[1]:=source; {加入初始结点，list为待扩展结点的表}

head:=0; {队首指针}

foot:=1; {队尾指针}

REPEAT

head:=head+1;

FOR x:=1 to 规则数 DO

BEGIN

根据规则产生新结点nw;

IF not_appear(nw,list) THEN {若新结点队列中不存在，则加到队尾}

BEGIN

foot:=foot+1;

list[foot]:=nw;

list[foot].father:=head;

IF list[foot]=目标结点 THEN 输出；

END；

END；

UNTIL headfoot; {队列为空表明再无结点可扩展}

dfs算法是什么？

DFS是深度优先搜索算法。

深度优先搜索算法，又称DFS(Depth First Search)。DFS算法是一种搜索算法，而搜索算法实质上是一种枚举，即借助计算机的高性能来有目的地枚举一个问题的部分情况或这个问题的所有情况，进而求出问题的解的一种方法。

分类：

1、 顺序性剪枝

若一些题的搜索顺序对答案无影响，那么搜索顺序的不同会导致搜索树形态的改变，优先搜索分支较少的阶段，此时能减少搜索的规模。

2、 重复性剪枝

在搜索的时候如果有多种方式可以到达一个状态，那么只需要搜索一个分支就可以了。

3、 可行性剪枝

可行性剪枝是对搜索正确性的一个保证，当分支在递归边界的时候回溯。

dfs算法是什么?

dfs算法是深度优先搜索。

深度优先搜索属于图算法的一种，英文缩写为DFS。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

深度优先搜索是一种在开发爬虫早期使用较多的方法，它的目的是要达到被搜索结构的叶结点（即那些不包含任何超链的HTML文件）。

主要思想

借用一个邻接表和布尔类型数组（判断一个点是否查看过，用于避免重复到达同一个点，造成死循环等），先将所有点按一定次序存入邻接表，再通过迭代器，对邻接表的linklist和布尔数组做出操作，从而达到不重复递归遍历的效果。

关于深度优先算法和深度优先算法会的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。