BFS

简介

找到两样东西之间的最短距离。

• 迷宫路径
• 国际跳棋AI
• 根据人际关系找到关系最近的医生

可以解决的问题

• 有没有路径

• 那条路径最短

核心思路

例如人际关系找到关系最近的医生

建模

首先要建模，创建一度关系，二度关系

代码中可以种HashSet模拟

查找

首先搜索一度关系，然后才是二度关系

使用队列存储待遍历的节点。

首先将一度关系，加入队列，

然后出队列，将出队列元素的关系降入到队列末尾

伪代码

Queue queue;
while(!queue.isEmpty())
{
	// 去节点
	curr = queue.poll();
	// 将孩子节点加入队列末尾
	qeue.addAll(curr.chirend);
}

为了防止死循环(A-B,B-A)，还有结束状态还要加入检测机制

改进后

Queue queue;
Set visted;
while(!queue.isEmpty())
{
	// 去节点
	curr = queue.poll();
	//是否结束
	if(curr == end)
	{
		return;
	}
	//已经遍历过 不加入队列
	if(visted.contains(curr))
	{
		continue;
	}
	// 将孩子节点加入队列末尾
	qeue.addAll(curr.chirend);
}

为了输出路径，要加上指向上一节点的机制，然后可以根据最后一个节点找到每一个节点。

Queue queue;
Set visted;
while(!queue.isEmpty())
{
	// 去节点
	curr = queue.poll();
	//是否结束
	if(curr == end)
	{
		return;
	}
	//已经遍历过 不加入队列
	if(visted.contains(curr))
	{
		continue;
	}
	//孩子节点的上一步 保存
	for(t:curr.chirend)
	{
		t.pre = curr;
	}
	// 将孩子节点加入队列末尾
	qeue.addAll(curr.chirend);
}