两种优先搜索

深度优先搜索

深度优先搜索采用的是，从首节点出发，一直朝一个方向进行访问相邻节点，直到该方向无相邻节点可以访问为止，这时回到上一节点，从上一节点换一个继续访问，依次重复。直到访问到想要找到的节点，或所有节点全部访问完成。

深度优先搜索的算法模型为：

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

可以看到深度优先搜索，利用的是递归的思想，每次都向深一层访问，直到无法访问。需要注意的是边界条件的判断和尝试吗，每一种可能之后的回溯。

广度优先搜索

广度优先搜索与深度不同，不是采用递归的思路，而是利用了数据结构中的“队列”结构。访问队头元素，将其相邻节点进队，全部相邻元素进栈完成，队头出队。依次重复，直到找到目标节点，或者全部节点被访问完成（也即队列为空）。

深度优先搜索的算法模型为：

void dfs(){
   while (head<tail){
       判断边界
       尝试每一种可能 for(i=1;i<n;i++){
           入队
       }
       出队队头
   }
}

以迷宫问题为例

深度优先

void dfs(int x, int y,int step) {
	if (x == e_x-1 && y == e_y-1) {
	/*找到了终点*/
		if (step < min) min = step;
		return;
	}
	for (int i = 0; i < 4; i++) {
	/*directio数组存储四个方向*/
		int tempx = x + direction[i][0];
		int tempy = y + direction[i][1];
		if (tempx < 0 || tempy < 0 || tempx >= r || tempy >= c) {
		/*越界*/
			continue;
		}
		if (status[tempx][tempy] == 1 || container[tempx][tempy] == 1) {
		/*遇到障碍或走过*/
			continue ;
		}
		{
			status[tempx][tempy] = 1;
			dfs(tempx, tempy, step + 1);
			status[tempx][tempy] = 0;
			/*回溯*/
		}


	}
	return;

}

广度优先

int bfs(int x,int y,int step) {
	way[tail].x = x;
	way[tail].y = y;
	way[tail].step = 0;
	tail++;
	book[x][y] = 1;
    /*首先入队起点*/
	while (tail>head)
	/*终止条件：队列为空*/
	{	
		int flag = 0;//找到节点标志
		for (int i = 0; i < 4; i++) {
			int tempx = way[head].x + direction[i][0];
			int tempy = way[head].y + direction[i][1];
			
			if (error(tempx, tempy)) continue;
			/*越界*/
			if (book[tempx][tempy] == 1 || container[tempx][tempy] == 1) continue;
			/*障碍或走过*/
			else {
				if (tempx == e_x-1 && tempy == e_y-1) {
					flag = 1;
					break;
				}
				else {
					book[tempx][tempy] = 1;
					way[tail].x = tempx;
					way[tail].y = tempy;
					way[tail].step = way[head].step+1;
					tail++;//入队新元素
				}
			}
		}
		if (flag == 1) break;
		head++;//队头元素出队
	}
	
	return way[tail-1].step;
}