深度优先搜索：

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

深度优先搜索所使用的策略就如其名字一样，只要可能，就在图中尽量的深入。深度优先搜素总是对最近才发现的结点V 的出发边进行探索，直到该结点的所有出发边都被发现为止。一旦结点V 的所有出发边都被发现，搜索则回溯到V 的前驱结点（V 是经过该点才被发现的），来探索该前驱结点的出发边。

   该过程一直持续到从源结点可以到达的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新的源节点，并重复同样的搜索过程。

深度优先遍历图的基本思路是，从图中某顶点V 出发：

   （1）访问顶点V 。

   （2）依次从V 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和 v 有路径相通的顶点都被访问。

   （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

下面采用一个示例图来说明这个过程。如图所示，示例图是一个无向图，如果我们从A 点发起深度优先搜索（以下的访问次序并不是唯一的，第二个点既可以是B 也可以是C ，D ），则我们可能得到如下的一个访问过程：AB E（没有路了！回溯到 A ) C F H G D（没有路，最终回溯到A ，A 也没有未访问的相邻节点，本次搜索结束）。