深度优先搜索深度优先搜索是一种在开发爬虫早期使用较多的方法。
它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。
在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。
深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。
当不再有其他超链可选择时，说明搜索已经结束。
事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.举例说明之：下图是一个无向图，如果我们从A点发起深度优先搜索（以下的访问次序并不是唯一的，第二个点既可以是B也可以是C,D），则我们可能得到如下的一个访问过程：A->B->E（没有路了。

回溯到A)->C->F->H->G->D（没有路，最终回溯到A,A也没有未访问的相邻节点，本次搜索结束）.简要说明深度优先搜索的特点：每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的\"结束时间\"排序（具体做法是创建一个list，然后在每个节点的相邻节点都已被访问的情况下，将该节点加入list结尾，然后逆转整个链表)，则我们可以得到所谓的\"拓扑排序\",即topological sort. 步骤深度优先搜索（DFS)有两个重要的点：第一是当前怎么做，第二是下一步怎么做；模板如下：public static void dfs (int step) { //判断边界，递归出口 //遍历每一种可能，经进行递归 for (int i = 1; i < n; i++) { dfs(step + 1); } }1. find(方向：right) 在当前层寻找满足要求的节点（剪枝）。
这一步需要构建剪枝的要求；2. forward(方向：down)当前节点满足要求，就进入下一层，重新开始find操作；3. done(方向：right)当前节点满足要求，且到达最后一层，得到结果，并进入下一个节点，开始find；4. back(方向：up)当遍历完了一个节点所有子节点时，就回溯到当前节点的兄弟节点，开始find。
思路深度优先遍历图的方法是，从图中某顶点v出发：（1）访问顶点v；（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
　当然，当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法，那就是广度优先搜索(BFS).算法伪代码bool visited[MaxVnum];void DFS(Graph G,int v){ visited[v]= true; //从V开始访问，flag它 printf(\"%d\",v); //打印出V for(int j=0;j<G.vexnum;j++) if(G.arcs[v][j]==1&&visited[j]== false) //这里可以获得V未访问过的邻接点 DFS(G,j); //递归调用，如果所有节点都被访问过，就回溯，而不再调用这里的DFS} void DFSTraverse(Graph G) { for (int v = 0; v < G.vexnum; v++) visited[v] = false; //刚开始都没有被访问过 for (int v = 0; v < G.vexnum; ++v) if (visited[v] == false) //从没有访问过的第一个元素来遍历图 DFS(G, v);}c++源码#include<iostream>#include<vector>#include<stack>#include<memory.h> using namespace std; vector<vector<int>> tree;//声明一个二维向量int flag[10];//用于搜索到了节点i的第几个节点stack <int>stk;//声明一个堆栈int ar_tree[8] = { 1,1,1,3,5,3,5,7 };void DFS(int node) {cout << node <<\" \";if (flag[node] == 0) {stk.push(node);}int temp;//判断node的子节点是否搜索完成if (flag[node] < tree[node].size()) {temp = tree[node][flag[node]];flag[node]++;DFS(temp);}else {//若已经完成stk.pop();//弹出子节点if (!stk.empty()) {//若堆栈不为空temp = stk.top();//取此时的栈顶元素，即为node的上一级节点DFS(temp);}}}int main() {ios::sync_with_stdio(false);memset(flag, 0, sizeof(flag));register int i,temp;tree.resize(10);//图中的数共有九个节点//生成树for (i = 2; i <=9; i++) {temp = ar_tree[i - 2];tree[temp].push_back(i);//表示第i个节点为第temp个节点的子节点}//DFScout << \"DFS过程：\" << endl;DFS(1);cout << endl;return 0;}c#using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace DFS{ class Program { public int[,] map = new int[100, 100]; public int[] road = new int[120]; public int n, x, y; public int m = 1; public int[] visited = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }; static void Main(string[] args) { Program pro = new DFS.Program(); int i, j; pro.n = int.Parse(Console.ReadLine()); pro.x= int.Parse(Console.ReadLine()); pro.y= int.Parse(Console.ReadLine()); for (i = 0; i < pro.n; i++) { for (j = 0; j < pro.n; j++) { pro.map[i,j]= int.Parse(Console.ReadLine()); } } pro.road[0] = pro.x; pro.dfs(pro.x); } public void dfs(int p) { visited[p] = 1; int i, j; for (i = 0; i < n; i++) { if (map[p,i] == 1 && visited[i] == 0) { if (i == y)///如果深搜到了终点，就输出刚才经过的路径 { for (j = 0; j < m; j++) { Console.WriteLine(\"{0}\", road[j]); } Console.WriteLine(\"{0}\r\n\", y); } else///如果该点不是终点 { map[p,i] = 0; road[m] = i;///将该点存起来 m++; dfs(i);///接着深搜 map[p,i] = 1; visited[i] = 0; m--; } } } } }}