栈实现深度优先遍历算法

⑴ 用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法

使用栈来实现算法。

用邻接表表示图进行深度优先遍历时，通常采用栈来实现算法，广度遍历使用队列。

扩展材料：

深度优先遍历：类似与树的前序遍历。从图中的某个顶点v出发，访问此顶点，然后从v的未被访问到的邻接点进行遍历，直到图中所有和v有路径相通的顶点都被访问到

注：优先访问外层节点，访问到无新顶点时，会进行回退，访问未被访问过的分支顶点。

广度优先遍历：类似于树的层序遍历。从图中的某个顶点w出发，让顶点w入队，然后顶点w再出队，并让所有和顶点w相连的顶点入队，然后再出队一个顶点t，并让所有和t相连但未被访问过的顶点入队……由此循环，指定图中所有元素都出队。

参考资料来源：

知网论文-数据结构中图的遍历算法研究

⑵ 基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）

        深度优先搜索和广度优先搜索，都是图形搜索算法，它两相似，又却不同，在应用上也被用到不同的地方。这里拿一起讨论，方便比较。

一、深度优先搜索

        深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

基本步奏

（1）对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。

（2）从stack中访问栈顶的点；

（3）找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行；

（4）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进行；

（5）直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。

二、广度优先搜索

        广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。

基本步奏

（1）给出一连通图，如图，初始化全是白色（未访问）；

（2）搜索起点V1（灰色）；

（3）已搜索V1（黑色），即将搜索V2，V3，V4（标灰）；

（4）对V2，V3，V4重复以上操作；

（5）直到终点V7被染灰，终止；

（6）最短路径为V1，V4，V7.

⑶ 数据结构问题：图的深度优先遍历中有递归的应用，要用到栈，图中顶点是如何出栈进栈的是进栈时访问还是

首先你得明白函数调用本身就是通过栈来实现的。 调用函数是入栈，而函数返回是出栈。
为什么是栈， 你要知道栈的特性是 “后进先出”或者是“先进后出”， 而对于函数调用来说， 一定会有最先调用的函数，最后才返回。 举个例子： 函数a,b,c,d的调用关系是a调用b，b又调用c，c又调用d， 那么当d函数执行完后，它会返回到c，同时c执行完成后返回到b，最后返回到a。
所以函数调用的顺序是a->b->c->d
函数返回的顺序是d->c->b->a
很明显 想要实现这种效果就要依靠栈。
因此函数调用过程是有一个叫做“调用栈”来实现的。
递归函数同理，只不过上边的a,b,c,d全变成同一个函数a->a->a->a，为了人为能区分清楚，不防给a函数加上角标，来标记是第几层调用a1->a2->a3->a4 ，返回时a4->a3->a2->a1 这就是递归函数调用返回过程。
接下来 深度优先搜索（dfs）本身就是靠函数递归调用实现的。
对于一个图来说，是由结点和边构成的， 在存储时就需要用到
struct node {
int data;
struct node * next[CNT];
}
上边只是一种简单的定义，对一个结点来说主要就是2部分， 一为它所存的数据是什么（数据域），二为它能指向哪些其它的边（指针域）。
你问了这样的问题：这些顶点怎么进出栈？又是如何访问的？
这里我要解释下访问的意义， 访问应该是对节点的数据域进行某种操作， 一定要理解这句话，是对数据域进行某种操作， 对于上边定义的结构 data就是数据域， 我需要对data进行某种操作，比如调用printf输出data， 这就是一种操作， 而只有对data进行了printf之后才能说“访问了这个结点”， 否则，单纯的使用了节点的指针域不能说访问了节点。
因此，如何访问节点的， 什么时候访问的，就要由你来定，
如果是下面这样的写法：
void dfs(struct node* n)
{
if (n->next[0] == NULL) {
return ;
}
for (int i = 0; n->next[i] != NULL; i++) {
dfs(n->next[i]);

}
printf ("%d\n", n->data);
}
你可以看到，printf是在 dfs函数递归调用 “返回”的时候才会被调用，换句话说， 图中所有节点在从开始走到不能再往下走的一个节点时(某个节点没有指向其它指点的边了），返回，同时输出该节点的data。 这种情况下是“出栈时访问”
而当printf换到if语句前头时，则是“入栈时访问”。
这如同二叉数的三种顺序遍历，前、中、后序遍历区别在于 何时访问节点
如下是前序遍历
void preorder(node* n)
{
printf(n->data);

preorder(n->left);
preorder(n->right);

}
如下是后序遍历
void afterorder(node* n)
{
afterorder(n->left);
afterorder(n->right);

printf(n->data);
}
如下是中序遍历
void inorder(node* n)
{
inorder(n->left);
printf(n->data);
inorder(n->right);
}

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

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

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

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


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

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

定义节点

class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
递归的方式

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

class Solution{
public void (TreeNode root){
if(root == null){
return;
}
System.out.print(root.val +"->");
(root.left);
(root.right);
}
}
迭代的方式

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

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

class Solution{
public void (TreeNode root){
if(root == null) return;
Stack<TreeNode> 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个方向递归。