深度优先搜索

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的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个节点的子节点
	}
	//DFS
	cout << "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--;
 }
 }
 }
 }
 }
}