双向搜索

一、双向搜索

当给出了起点状态与终点状态时，使用普通的搜索从起点向下搜索，则效率会很低，搜索树会非常庞大；

所以，可以使用双向搜索，及从起点与终点同时向中间搜索，搜索到同一个状态时，将从起点与终点搜索的值相加得到最终值的搜索；

一般给出 “始态” 与 “终态” 时，可以考虑使用双向搜索；

二、双向DFS

第一个 $DFS$ 时，先搜索前一半的空间，存储所有可达的值；

第二个 $DFS$ 时，再搜索后一半的空间，然后查询是否在前一半空间中出现过；

三、双向BFS

双向 $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) {找到答案，搜索结束;}}
}

也可以只使用一个对列，即在队列中再开一个变量标记从何处开始搜索的即可；

四、例题

导航系统

题目

小Q来到了一个随机的国度。这个国度由n座城市和m条双向道路构成。因为这个国度崇尚随机，因此m条边是用随机选择两端点的方式生成的。充满好奇的小Q想在这里进行k次随机的旅行，每次的起点和终点也是随机选择的。在每次出发之前，他会使用导航系统计算两点间最少需要经过几条道路。请写一个程序，帮助小Q计算两点间的最短路

输入

第一行包含3个正整数n,m,k(2<=n<=100000,1<=m<=300000,1<=k<=10000)，分别表示点数、边数和询问数。

接下来m行，每行两个正整数u_i,v_i(1<=u_i,v_i<=n)，表示一条双向道路。输入数据保证不会有重边和自环。

接下来k行，每行两个正整数u_i,v_i(1<=u_i,v_i<=n)，表示一次询问。

输入数据保证随机生成，且除了样例之外均满足n=100000,m=300000。

本题共3组数据。

输出

输出k行，每行一个整数，即最少经过的边数，若无解输出-1。

思路

此题给出一个起点与一个终点，所以考虑双向搜索，状态扩展时，扩展每个点相连的点；

使用邻接表记录图，在询问时，使用并查集判断两点是否连通；

代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAXN 300005
using namespace std;
int n, m, k, father[MAXN];
bool flag1[MAXN], flag2[MAXN];
vector < int > g[MAXN];
struct node {int x, z, f;
};
void firstset(int n) {for (int i = 1; i <= n; i++) {father[i] = i;}return;
}
int findset(int x) {if (x == father[x]) return x;return father[x] = findset(father[x]);
}
void push(int x, int y) {father[findset(x)] = findset(y);return;
}
int bfs(int s, int e) {queue < node > q;memset(flag1, false, sizeof(flag1));memset(flag2, false, sizeof(flag2));flag1[s] = true, flag2[e] = true;q.push( node ( { s, 0, 1 } ) );q.push( node ( { e, 0, 2 } ) );while (!q.empty()) {node t = q.front();q.pop();for (int i = 0; i < g[t.x].size(); i++) {if (t.f == 1) {flag1[g[t.x][i]] = true;q.push( node ( { g[t.x][i], t.z + 1, 1 } ) );} else {flag2[g[t.x][i]] = true;q.push( node ( { g[t.x][i], t.z + 1, 2 } ) );}if (flag1[g[t.x][i]] == true && flag2[g[t.x][i]] == true) {int ans = t.z + 1;if (t.f == 2) {while (!q.empty()) {node z = q.front();if (z.x == g[t.x][i] && z.f == 1) {ans += z.z;break;}q.pop();}} else {while (!q.empty()) {node z = q.front();if (z.x == g[t.x][i] && z.f == 2) {ans += z.z;break;}q.pop();}}return ans;}}}
}
int main() {scanf("%d %d %d", &n, &m, &k);firstset(n);for (int i = 1; i <= m; i++) {int x, y;scanf("%d %d", &x, &y);g[x].push_back(y);g[y].push_back(x);push(x, y);}for (int i = 1; i <= n; i++) {sort(g[i].begin(), g[i].end());}for (int i = 1; i <= k; i++) {int x, y;scanf("%d %d", &x, &y);if (x == y) printf("0\n");else if (findset(x) != findset(y)) printf("-1\n");else printf("%d\n", bfs(x, y));}return 0;
}