【C++】算法集锦（5）：BFS算法

int BFS(Node start,Node target){
	/*
		这是一个BFS算法的代码框架
		return：返回从start到target的最短步数
		start：起始点
		target：终点
	*/
	
	Queue<Node> q;
	Set<Node> visited;	//避免走回头路
	
	q.offer(start);	//将起点加入队列
	visited.add(start);
	int step = 0;	//纪录扩散的步数

	while(q not empty){
		int sz = q.size();
		for(int i = 0; i<sz; i++){
			Node cur = q.poll();

			//判断是否到终点
			if(cur is target)
				return step;
			
			//将cur相邻节点加入队列
			for(Node x: cur.adj())	//cur.adj()泛指与cur相邻的节点
				if(x not in visited){
					q.offer(x);
					visited.add(x);
				}
		}	
		step++;	//更新步数
	}
}

int minDepth(TreeNode root){
	/*
		这是一个求二叉树最小高度的函数
		return：二叉树的最小高度
		root：根节点
	*/
	if(root == NULL) return 0;
	
	Queue<TreeNode> q;

	q.offer(root);	//将起点加入队列
	int depth = 1;	

	while(!q.isEmpty()){
		int sz = q.size();
		for(int i = 0; i<sz; i++){
			TreeNode cur = q.poll();

			//判断是否到终点
			if(cur.left == NULL && cur.right == NULL)
				return depth;
			
			//将cur相邻节点加入队列
			if(cur.left != NULL)
				q.offer(cur.left);
			if(cur.right != NULL)
				q.offer(cur.right);
		}	
		depth++;	//更新步数
	}
	return depth;
}

第一步，拨一下。不管会怎么样，都得拨一下吧。这一下有八种可能了吧。
第二步，匹配。拨一下，对所有结果都进行一次的匹配。如果对上了，就返回结果；如果对不上，返回第一步再循环。
注意点一：如果碰到死亡密码，跳过。
注意点二：不要走回头路。
注意点三：空间能省着用就省着用。

int openLock(String[] deadends,String target){
	//纪录需要跳过的死亡密码
	Set<String> deads = new HashSet<>();
	
	for(String s:deadends) 
		dead.add(s);

	//纪录已经穷举过的密码
	set<String> visited = new HashSet<>();
	
	Queue<String> q = new LinkedList<>();
	
	//从起点开始启动广度优先搜索
	int step = 0;
	q.offer("0000");
	visited.add("0000");

	while(!q.isEmpty){
		int sz = q.size();
		for(int i = 0;i<sz;i++){
			string cur = q.poll();
				
			//判断密码是否合法
			if(deads.contains(cur)
				continue;
			if(cur.equals(target))
				return step;
		}

		//将一个节点的未遍历相邻节点加入队列
		for(int j=0;j<4;j++){
			String up = plusOne(cur,j);
			if(!visited.contains(up){
				q.offer(up);
				visited.add(up);
			}
			String down = minusOne(cur,j);
			if(!visited.contains(down){
				q.offer(down);
				visited.add(down);
			}
		}
		step++;
	}
	return -1;
}

String plusOne(String s,int j){
	char[] ch = s.toCharArray();
	if(ch[j] == '9')
		ch[j] = '0';
	else
		ch[j] += 1;
	return new String(ch);
}

String downOne(String s,int j){
	char[] ch = s.toCharArray();
	if(ch[j] == '0')
		ch[j] = '9';
	else
		ch[j] -= 1;
	return new String(ch);
}