深度优先搜索（dfs）算法之一——基础
1.1 深度优先搜索（dfs）定义
深度优先搜索(Depth-First Search)是图的一种搜索方式，以深度为优先级去进行搜索，通俗地说就是"不撞南墙不回头"，对于当前正在搜索的路径而言，只有把当前路径给搜索完了，即走到无路可走时，才回返回进而搜索另一条路。
1.2 深度优先搜索（dfs）算法思想
深度优先搜索是图的一种搜索方式，如上图所示，以深度为优先级去进行搜索，通俗地说就是"不撞南墙不回头",或者"一条路走到黑"——对于当前正在搜索的路径而言，只有把当前路径给搜索完了，即走到无路可走时，才回返回进而搜索另一条路。 深度优先搜索一般是通过递归来实现的，“递”的过程就是往下搜的过程对应着深度，“归”的过程就是回溯，回退上一级
DFS 不仅仅可以搜索图，还可以搜索树，搜索所有可以转换、抽象为图的数据结构。
假设我们有一个共有10个节点的二叉树，以下是DFS的搜索过程：
1、从 根节点开始向下搜索
2、搜索到2号节点
3、搜索到4号节点
4、搜索到7号节点
5、回溯到4号节点
6、回溯到2号节点
7、搜索到5号节点
8、搜索到8号节点
9、回溯到5号节点
10、搜索到9号节点，回溯到5号节点,回溯到2号节点,回溯到1号节点
11、搜索到3号节点
12、在逐层回溯到1号根节点
根据以上图示，可以分析出DFS的搜索过程是一个递归的过程，递归的过程就是往下搜的过程，回溯的过程就是回退上一级的过程。
深搜作为一种算法来说，并没有像二分、堆、快速排序等这些算法有固定的模板，它更像是一种思想。
1.3、基本模板框架
我们可以总结一个基本的DFS算法框架如下：
void dfs( int root){ //root 为起始节点
visit(root); //访问根节点
for( int i = 0; i < root->child.size(); i++){
dfs(root->child[i]); //递归访问子节点
}
}
int main(){
//建立树
dfs(root);
return 0;
}