深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。

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

例题一 等式ABC+DEF=GHI

描述

假设等式  ABC+DEF=GHI  成立，且 A~I 的取值范围皆为（0 ≤ N ≤ 9）。请计算等式共有有多少种不同的可能，并输出等式。

C++ Code

#include<iostream>
#include<Windows.h>
#include"function.h"
using namespace std;

int a[10], book[10], n = 0;//此处特别说明一下：C语言的全局变量在没有赋值以前默认为0，
						//因此这里的book数组无需全部再次赋初值0

void dfs(int step) {
	if (step == 10) {//如果是 dfs(10) 被调用的时候，就意味着前面9个数字已经被确定
		if (a[1] * 100 + a[2] * 10 + a[3] + a[4] * 100 + a[5] * 10 + a[6] == a[7] * 100 + a[8] * 10 + a[9])
		{
			n++;
			//cout <<a[1] << a[2] << a[3] << "+" << a[4] << a[5] << a[6] << "=" << a[7] << a[8] << a[9] << endl;
		}
		return;//返回之前的一步（最近调用的地方）
	}

	//按照1、2、3...n的顺序一一尝试
	for (int i = 1; i <= 9; i++) {
		//判断i是否已经用掉
		if (book[i] == 0) {
			a[step] = i;//将i填入等式
			book[i] = 1;//将book[i]设为1，表示i已经填入等式

			//等式中第step个变量已经确定，接下来进行下一轮
			dfs(step + 1);
			book[i] = 0;//将i从等式中撤回，才能进行下一次尝试
		}
	}
	return;
}

int main() {
	dfs(1);
	cout <<n / 2;//因为ABC+DEF=GHI和DEF+ABC=GHI是同一种情况

	system("pause");
	return 0;
}

例题二 迷宫最短路径

描述

假设迷宫的平面图如下所示，其中标记为 1 的为障碍物，标记为 0 的为可以通行的地方。

0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1

输入

n和m，代表迷宫地图的行数和列数，然后逐行输入迷宫地图，最后输入起点和终点坐标

输入样例

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3

输出

输出1个正整数，为最短路径的值。

C++ Code

#include<iostream>
#include<Windows.h>
#include"function.h"
using namespace std;

int n, m, p, q, min = 99999999;
int a[51][51], book[51][51];
void dfs(int x,int y,int step) {
	int next[4][2] = {
		{0,1},//向右走
		{1,0},//向下走
		{0,-1},//向左走
		{-1,0} //向上走
	};

	int tx, ty, k;
	//判断是否到达小哈的位置
	if (x==p && y==q) {
		//更新最小值
		if(step<min){
			min = step;
		}
		return;//这里的返回很重要
	}

	//枚举四种走法
	for (k = 0; k <= 3;k++) {
		//计算下一个点的坐标
		tx = x + next[k][0];
		ty = y + next[k][1];
		//判断是否越界
		if (tx<1 || tx>n || ty<1 || ty>m) {
			continue;
		}
		//判断该点是否为障碍物或者已经在路径中
		if (a[tx][ty]==0 && book[tx][ty]==0) {
			book[tx][ty] = 1;//标记整点已经走过
			dfs(tx, ty, step + 1);
			book[tx][ty] = 0;//尝试结束，取消这个点的标记
		}
	}
	return;
	
}

int main() {
	int i, j, startx, starty;
	//读入n和m，n为行，m为列
	cin >> n >> m;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	//读入起点和终点坐标
	cin >> startx >> starty >> p >> q;

	//从起点开始搜索
	book[startx][starty] = 1;//标记起点已在路径中，防止后面重复走
	//第一个参数是起点的x坐标，第二个参数是起点的y坐标，第三个参数是初始步数为0
	dfs(startx, starty, 0);

	//输出最短步数
	cout << min;
	system("pause");
	return 0;
}

dfs的基本模型大概是这样子

dfs(int step) {
	判断边界
	尝试每一种可能for(i = 1; i <= n; i++)
	{
		继续下一步dfs(step + 1);
	}
	返回
}