关于BFS和DFS的一些了解

BFS：宽度优先，创建两个分别为OPEN和CLOSE的容器，用来标记是否已搜索过(可以用队列或链表等实现，如上图)。对于当前节点来说，对OPEN容器里的元素，先搜索所有与其距离为K的点，加入至CLOSE容器中，再搜索所有与其距离为K+1(举例)

的点，加入至CLOSE容器中，直到OPEN的元素为空。

DFS:深度优先。设定一个初始状态，从初始位置向下一直深入(状态转移)，直到达到最深处，此时回溯，每进行一次回溯就要进行一步是否符合条件的判断，直到回到初始状态-----不撞南墙不回头。

另外深入的时候是不需要判断的

BFS框架():

//BFS的抽象框架
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=100;
bool vst[maxn][maxn];//访问标记
int dir[4][2]={0,1,0,-1,1,0,-1,0};//方向向量(即上下左右)

struct State // BFS 队列中的状态数据结构
{
	int x,y;//坐标
	int Step_Counter;//搜索步数统计器
};

State a[maxn]; //创建结构体数组

//约束条件检验
bool CheckState(State s){ 
	if(!vst[s.x][s.y] &&...)//满足条件
		return 1;
	else //约束条件冲突
		return 0;

} 

void bfs(State st){
	queue<State> q;//BFS队列
	State now,next;//定义2个状态(当前和下一个)
	st.Step_Counter=0;//计步器清零
	q.push(st);//入队
	vst[st.x][st.y]=1;//标记为已访问
	while(!q.empty()){
		now=q.front(); //注:front函数时返回当前起始元素的引用
		if(now==G){//出现目标态，此时为Step_CounterDE的最小值，退出即可
			//做相关处理
			return;
		}
		for(int i=0;i<4;i++){
			next.x=now.x+dir[i][0];//按照规则生成下一个状态
			next.y=now.y+dir[i][1];//同理
			next.Step_Counter=now.Step_Counter+1;
			if(CheckState(next)){ //如果状态满足约束条件则入队
				q.push(next);
				vst[next.x][next.y];//访问标记
		}
		}
		q.pop()//队首元素出队
	}
	return;
}