深度优先遍历（DFS）
与 BFS 类似，深度优先搜索（DFS）也可用于查找从根结点到目标结点的路径,下面看看利用栈（stack）是怎么帮助实现DFS的。
深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来

1. 结点的处理顺序是什么？
在上面的例子中，我们从根结点 A 开始。

1. 首先，我们选择结点 B 的路径，并进行回溯，直到我们到达结点 E，我们无法更进一步深入。
2. 然后我们回溯到 A 并选择第二条路径到结点 C 。从 C 开始，我们尝试第一条路径到 E 但是 E 已被访问过。所以我们回到 C 并尝试从另一条路径到 F。
3. 最后，我们找到了 G。

总的来说，在我们到达最深的结点之后，我们只会回溯并尝试另一条路径。

因此，你在 DFS 中找到的第一条路径并不总是最短的路径。例如，在上面的例子中，我们成功找出了路径 A-> C-> F-> G 并停止了DFS。但这不是从 A 到 G 的最短路径。

2. 栈的入栈和退栈顺序是什么？
如上面的动画所示，我们首先将根结点推入到栈中；然后我们尝试第一个邻居 B 并将结点 B 推入到栈中；等等等等。当我们到达最深的结点 E 时，我们需要回溯。当我们回溯时，我们将从栈中弹出最深的结点，这实际上是推入到栈中的最后一个结点。
结点的处理顺序是完全相反的顺序，就像它们被添加到栈中一样，它是后进先出（LIFO）。这就是我们在 DFS 中使用栈的原因。

在大多数情况下，我们在能使用 BFS 时也可以使用 DFS。但是有一个重要的区别：遍历顺序。与 BFS 不同，更早访问的结点可能不是更靠近根结点的结点。因此，你在 DFS 中找到的第一条路径可能不是最短路径。

3. DFS算法模板

// 非递归模板（手动维护一个栈）
void dfs(Node* root) {

    map<int, int> visited;
    if(!root) return;

    stack<Node*> stackNode;
    stackNode.push(root);

    while (!stackNode.empty()) {
        Node* node = stackNode.top();
        stackNode.pop();
        if (visited.count(node -> val)) continue;
        visited[node -> val] = 1;

        for (int i = node -> children.size()-1; i >= 0; --i) {
            stackNode.push(node -> children[i]);
        }
    }
    return;
}

模板总结
深度优先搜索类型的题目一般分为主函数和辅助函数，主函数用于遍历所有的搜索位置，判断是否可以开始进行搜索，如果可以即在辅助函数中进行搜索。辅助函数使用递归or栈实现深度优先搜索。

小技巧
对于棋盘、网格类的搜索，大多数要搜索当前节点的上下左右和对角多个方向的遍历，我们可以使用一个数组表示方向，就拿搜索上下左右来讲，我们从正上放邻居节点开始顺时针搜索当前节点相邻节点，伪代码如下：

vector<vector<int>> grid; // 待搜索的矩阵
int row, col, r_size, c_size; // 当前节点的坐标和矩阵规格，假设已经有正常值
vector<int> dir{ -1,0,1,0,-1 };
for (int i = 0; i < 4; i++) { //分别遍历上、右、下、左节点
	int r = row + dir[i], c = col + dir[i + 1];
	if (r >= 0 && r < r_size && c >= 0 && c < c_size && grid[r][c] == 1) {
	    stk.push({r, c});
	    grid[r][c] = 0;
	}
}