文档介绍：深度优先搜索的搜索策略是：
尽可能“深”的搜索某一分支。在深度优先搜索中，对于最先发现的结点，如果还有以此为起点的未搜索边，则沿此边继续搜索下去。当结点V的所有边都已经被探寻过，搜索将回溯到发现点V的那条边的始结点。重复此过程直至源结点可到达的所有结点为止
1
2
4
5
7
3
6
8
深搜的顺序是：1-2-4-7---5-8---3-6
*
DFS_深度优先搜索
*
1
2
4
5
7
3
6
8
深搜的顺序是：1-2-4-7---5-8---3-6
伪代码：
void dfs(int u){
for(u的每一个子节点v){
dfs(v);
}
}
过程在可以看做是栈的结构
dfs(1) dfs(1) dfs(1) dfs(1) dfs(1) dfs(1) dfs(1) dfs(1)
dfs(2) dfs(2) dfs(2) dfs(2) dfs(2) dfs(3) dfs(3)
dfs(4) dfs(4) dfs(5) dfs(5) dfs(6)
dfs(7) dfs(8)
树的深搜
*
DFS_深度优先搜索
*
H
A
L
I
F
B
C
D
E
J
G
K
S
*
DFS_深度优先搜索
*
图的深搜
Hdu 1241
题目大意：给定一个图，上边有*和@两种标记，其中@表示石油，好多@连在一起可以看成一个大的石油区，问在这个区域中有多少个石油区
int dx[8]={-1,-1,-1,0,1,1, 1, 0};
Int dy[8]={-1, 0, 1,1,1,0,-1,-1};
Void dfs(int x,int y){
g[x][y]=‘*’;
for(int i = 0; i < 8; i++){
xx = x + dx[i] ;
yy = y + dy[i] ;
if(xx < 0 || yy < 0 || xx >= m || yy >= n )
continue ;
if(g[xx][yy]=='@')
dfs(xx , yy) ;
}
}
0 1 2
7 _ 3
6 5 4
y
x
*
DFS_深度优先搜索
*
POJ 2676
题意：数独，找出一个可行解即可
（数独规则：：把一个9行9列的网格，再细分为9个3*3的子网格，要求每行、每列、每个子网格内都只能使用一次1~9中的一个数字，即每行、每列、每个子网格内都不允许出现相同的数字。）
0是待填位置，其他均为已填入的数字。
粗暴的方法 DFS加回溯
大概的框架：
dfs(int x,int y){
for(int i=1;i<=9;i++){
if(这个位置能填 i ){
g[x][y]=i;
(找到下一个为0的位置为(xx,yy));
dfs(xx,yy);
g[x][y]=0;
}
}
}
*
DFS_深度优先搜索
*
Dfs的优化
剪枝：在求解问题的时候，有时没必要将所有的可能结果都搜索一遍。如果在搜索一个新的节点的时候，如果可以判断到这一个节点不会得到解或是最优解