双向广搜

在算法竞赛中，双向 BFS（Bidirectional BFS）是解决起点和终点明确的无权图最短路径问题的高频优化算法，其核心是通过从起点和终点同时搜索将时间复杂度从𝑂(𝑎𝑏)降低到𝑂(𝑎𝑏/2).

单向搜索

如果我们用常规的搜索方法，从起点开始往下搜，那得到的解答树可能非常庞大，这样漫无目的的搜索就像大海捞针

双向搜索

但如果我们知道了起点和终点，分别从这两点同时开始搜索，直至在某一点相遇，这样做极大的提高了代码的运行效率

双向BFS维护两个对列，q1 ，q2 ，q1维护从起点开始搜索的状态，q2维护从终点开始搜索的状态，若在扩展状态时发现某个状态同时被q1 和q2扩展到，此时找到的即为答案；

将开始状态放入q1;
将结束状态放入q2;
将开始状态标记为1;
将结束状态标记为2;
while (q1不为空 && q2不为空) {if (q1大小 > q2大小) {取队列 q2 队首元素;} else {取队列 q1 队首元素;}循环遍历取出元素的可扩展状态 {if (从q1取出) {标记为1，放入q1队列;} else {标记为2，放入q2队列;}if (该状态同时被标记为1与2) {找到答案，搜索结束;}}
}