DFS，depth-first search，深度优先搜索。顾名思义，从一个节点出发，尽可能往下遍历，即尽可能离“家”远一点，这个思想其实就是树结构遍历中的先序遍历。

那么从上述话语中，我们可以很容易地判断出需要用到递归，其实DFS的常规构造方法也就是用到递归的，但是我们还要考虑到一个问题，那么就是如果一个图足够大，比如有上万个节点，上万条边，那么估计用递归运行DFS我们的电脑会瞬间卡死。。。因为递归的代价实在是太大了，图如果小一点还好，不是特别明显，一旦图过大，递归的劣势会被无限放大，因此这里除了用递归来构造DFS以外，我还会介绍非递归的方法，即通过使用数据结构——栈来代替函数调用，虽说栈的出现会导致占用过多的内存空间，但是，时代变了！区区一个栈再大能够有多大呢？再宝贵能有时间宝贵吗？所以在大型的图深度遍历中，使用栈的DFS绝对要比使用递归的DFS的效率要高！

递归算法转化为非递归算法的优点：

首先我们需要考虑到一些特殊情况：

解决完这些特殊情况之后，那么接下来就进入到了正式环节：

因为伪代码没有其他语言的语法限制，能够有助于我们更好地将注意力放在算法上，所以我们先用伪代码来讲述一下主要思想：