本篇将会结合实例解析双向搜索。
一、双向搜索
当给出了起点状态与终点状态时，使用普通的搜索从起点向下搜索，则效率会很低，搜索树会非常庞大；所以，可以使用双向搜索，及从起点与终点同时向中间搜索，搜索到同一个状态时，将从起点与终点搜索的值相加得到最终值的搜索；
一般给出“始态”与“终态”时，可以考虑使用双向搜索；
二、双向DFS
第一个DFS时，先搜索前一半的空间，存储所有可达的值；
第二个DFS时，再搜索后一半的空间，然后查询是否在前一半空间中出现过；
三、双向BFS
双向BFS维护两个对列，q1 ，q2 ，q1维护从起点开始搜索的状态，q2维护从终点开始搜索的状态，若在扩展状态时发现某个状态同时被q1 和q2扩展到，此时找到的即为答案；
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | 将开始状态放入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。
思路：
此题给出一个起点与一个终点，所以考虑双向搜索，状态扩展时，扩展每个点相连的点；
使用邻接表记录图，在询问时，使用并查集判断两点是否连通；
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | #include <cstdio>#include <vector>#include <cstring>#include <queue>#include <algorithm>#define MAXN 300005using 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;} |
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程