本篇將會(huì)結(jié)合實(shí)例解析雙向搜索。

一、雙向搜索

當(dāng)給出了起點(diǎn)狀態(tài)與終點(diǎn)狀態(tài)時(shí)，使用普通的搜索從起點(diǎn)向下搜索，則效率會(huì)很低，搜索樹會(huì)非常龐大；所以，可以使用雙向搜索，及從起點(diǎn)與終點(diǎn)同時(shí)向中間搜索，搜索到同一個(gè)狀態(tài)時(shí)，將從起點(diǎn)與終點(diǎn)搜索的值相加得到最終值的搜索；

一般給出“始態(tài)”與“終態(tài)”時(shí)，可以考慮使用雙向搜索；

二、雙向DFS

第一個(gè)DFS時(shí)，先搜索前一半的空間，存儲(chǔ)所有可達(dá)的值；

第二個(gè)DFS時(shí)，再搜索后一半的空間，然后查詢是否在前一半空間中出現(xiàn)過；

三、雙向BFS

雙向BFS維護(hù)兩個(gè)對(duì)列，q1 ，q2 ，q1維護(hù)從起點(diǎn)開始搜索的狀態(tài)，q2維護(hù)從終點(diǎn)開始搜索的狀態(tài)，若在擴(kuò)展?fàn)顟B(tài)時(shí)發(fā)現(xiàn)某個(gè)狀態(tài)同時(shí)被q1 和q2擴(kuò)展到，此時(shí)找到的即為答案；

將開始狀態(tài)放入q1;
將結(jié)束狀態(tài)放入q2;
將開始狀態(tài)標(biāo)記為1;
將結(jié)束狀態(tài)標(biāo)記為2;
while (q1不為空 && q2不為空) {
    if (q1大小 > q2大小) {
        取隊(duì)列 q2 隊(duì)首元素;
    } else {
        取隊(duì)列 q1 隊(duì)首元素;
    }
    循環(huán)遍歷取出元素的可擴(kuò)展?fàn)顟B(tài) {
        if (從q1取出) {
    		標(biāo)記為1，放入q1隊(duì)列;
    	} else {
			標(biāo)記為2，放入q2隊(duì)列;
        }
        if (該狀態(tài)同時(shí)被標(biāo)記為1與2) {
            找到答案，搜索結(jié)束;
        }
    }
}

也可以只使用一個(gè)對(duì)列，即在隊(duì)列中再開一個(gè)變量標(biāo)記從何處開始搜索的即可；

四、例題

導(dǎo)航系統(tǒng)

題目：小Q來到了一個(gè)隨機(jī)的國度。這個(gè)國度由n座城市和m條雙向道路構(gòu)成。因?yàn)檫@個(gè)國度崇尚隨機(jī)，因此m條邊是用隨機(jī)選擇兩端點(diǎn)的方式生成的。充滿好奇的小Q想在這里進(jìn)行k次隨機(jī)的旅行，每次的起點(diǎn)和終點(diǎn)也是隨機(jī)選擇的。在每次出發(fā)之前，他會(huì)使用導(dǎo)航系統(tǒng)計(jì)算兩點(diǎn)間最少需要經(jīng)過幾條道路。請(qǐng)寫一個(gè)程序，幫助小Q計(jì)算兩點(diǎn)間的最短路。

輸入：

第一行包含3個(gè)正整數(shù)n,m,k(2<=n<=100000,1<=m<=300000,1<=k<=10000)，分別表示點(diǎn)數(shù)、邊數(shù)和詢問數(shù)。

接下來m行，每行兩個(gè)正整數(shù)u_i,v_i(1<=u_i,v_i<=n)，表示一條雙向道路。輸入數(shù)據(jù)保證不會(huì)有重邊和自環(huán)。

接下來k行，每行兩個(gè)正整數(shù)u_i,v_i(1<=u_i,v_i<=n)，表示一次詢問。

輸入數(shù)據(jù)保證隨機(jī)生成，且除了樣例之外均滿足n=100000,m=300000。

本題共3組數(shù)據(jù)。

輸出：

輸出k行，每行一個(gè)整數(shù)，即最少經(jīng)過的邊數(shù)，若無解輸出-1。

思路：

此題給出一個(gè)起點(diǎn)與一個(gè)終點(diǎn)，所以考慮雙向搜索，狀態(tài)擴(kuò)展時(shí)，擴(kuò)展每個(gè)點(diǎn)相連的點(diǎn)；

使用鄰接表記錄圖，在詢問時(shí)，使用并查集判斷兩點(diǎn)是否連通；

代碼如下：

#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;
}