之前我们介绍了广度优先搜索 ，今天我们来介绍深度优先搜索（Depth-First Search, aka DFS）算法。

这篇文章给出了深度优先搜索的算法描述，并用一个二叉树作为例子，用golang实现一个 深度优先遍历程序。

我们先来描述深度优先搜索算法：

       在图中选取一个节点作为根节点，将根节点入栈
               |
               V
   --> 当栈不为空时
  |            |
  |            V
  |    弹出栈顶元素E
  |            |
  |            V
  |    如果E没有搜索过，则判断E是否为目标节点，如果是，程序结束；
  |    如果E已经搜索过，则continue
  |            |
  |            V
  |    将E标记为已经搜索过
  |            |
  |            V
  |    将E所有的邻居节点入栈
  |            |
   ------------

我们把上述的算法描述稍稍进行修改，把“栈”改成“对列”，就可以得到之前学过的广度优先搜索的算法 描述：

       在图中选取一个节点作为根节点，将根节点入对列
               |
               V
   --> 当对列不为空时
  |            |
  |            V
  |    弹出对列顶元素E
  |            |
  |            V
  |    如果E没有搜索过，则判断E是否为目标节点，如果是，程序结束；
  |    如果E已经搜索过，则continue
  |            |
  |            V
  |    将E标记为已经搜索过
  |            |
  |            V
  |    将E所有的邻居节点入对列
  |            |
   ------------

在进行了算法描述之后，我们来看一个二叉树的例子。

             A
            / \
           B   C
          / \  / \
         D  E F   G

我们知道，树（Tree）是一种特殊的图（Graph），特殊之处在于树是自顶 向下的，没有边会从下面的节点指上来。也就是说，无论是DFS还是BFS，遍历 树这种数据结构是不会遇到重复结点的。

对于这个二叉树，如果我们用深度优先遍历，那么输出顺序为：A, B, D, E, C, F, G。 如果用广度优先遍历，那么输出顺序为：A, B, C, D, E, F, G。

这里是Golang的实现。

===================补充===================

DFS其实还是有一种更加简洁的算法描述，那就是它的递归形式，为了方便描述，我们假设函数名为dfsRecursive()：

1. 在图中选择一个节点做为根节点root
2. 如果节点为空或者节点已经搜索过，return false
3. 如果节点是目标节点，return true
4. dfsRecursive(root.leftNode)
5. dfsRecursive(root.rightNode)

以上。