C++ 算法学习——1.3 双向深度优先搜索

双向深度优先搜索（Bidirectional Depth-First Search）是一种图搜索算法，旨在通过从起始节点和目标节点同时开始，沿着深度优先搜索的路径向前探索，以减少搜索空间并提高搜索效率。

1. 基本原理

• 双向深度优先搜索同时从起始节点和目标节点开始搜索，通过交替地在两个方向上进行深度优先搜索，直到两个搜索路径相遇。

2. 算法步骤

1. 初始化两个空的栈，一个用于从起始节点开始的搜索，另一个用于从目标节点开始的搜索。
2. 将起始节点和目标节点分别推入两个栈。
3. 从两个栈中分别出栈一个节点，进行如下操作：
   • 标记节点为已访问。
   • 检查当前节点是否在两个搜索方向上相遇，如果相遇则搜索结束。
   • 否则，对当前节点的未访问邻居节点进行处理：
     • 对于起始节点搜索方向，将未访问的邻居节点推入起始栈。
     • 对于目标节点搜索方向，将未访问的邻居节点推入目标栈。
4. 重复步骤3，直到两个栈中的节点相遇或者两个栈都为空。

3. 优缺点

• 优点：
  • 相较于单向深度优先搜索，双向深度优先搜索在搜索空间较大时能够更快地找到目标节点。
• 缺点：
  • 需要额外的内存空间来维护两个搜索方向的栈。
  • 在特定情况下可能会比单向搜索更慢，例如在目标节点附近的情况。

代码示例（邻接表表示的图）：

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>using namespace std;// 无权图的邻接表表示
vector<vector<int>> graph;// 双向深度优先搜索函数
bool bidirectionalDFS(int start, int target) {stack<int> startStack, targetStack;unordered_set<int> startVisited, targetVisited;startStack.push(start);targetStack.push(target);while (!startStack.empty() && !targetStack.empty()) {int currentStart = startStack.top();int currentTarget = targetStack.top();startStack.pop();targetStack.pop();startVisited.insert(currentStart);targetVisited.insert(currentTarget);// 检查是否相遇if (startVisited.count(currentTarget) || targetVisited.count(currentStart)) {cout << "Nodes met at: " << (startVisited.count(currentTarget) ? currentTarget : currentStart) << endl;return true;}//对于std::unordered_set和std::unordered_map，count函数会返回1（存在）或0（不存在）。// 处理邻居节点for (int neighbor : graph[currentStart]) {if (!startVisited.count(neighbor)) {startStack.push(neighbor);}}for (int neighbor : graph[currentTarget]) {if (!targetVisited.count(neighbor)) {targetStack.push(neighbor);}}}cout << "Nodes did not meet." << endl;return false;
}

代码示例（矩阵模样，起点坐标begina,beginb,目标点坐标enda,endb）：

#include <iostream>
#include <stack>
#include <unordered_set>
using namespace std;
int n,m;
char** board;
void showcurboard()
{for(int i=0;i<n;i++){for(int j=0;j<m;j++)cout<<board[i][j];cout<<endl;}
}
struct PairHash {template <class T1, class T2>std::size_t operator () (const std::pair<T1, T2> &pair) const {auto hash1 = std::hash<T1>{}(pair.first);auto hash2 = std::hash<T2>{}(pair.second);return hash1 ^ hash2;}
};
// 双向深度优先搜索函数
bool bidirectionalDFS(int begina, int beginb, int enda, int endb) {stack<pair<int, int>> startStack, targetStack;unordered_set<pair<int, int>,PairHash> startVisited;unordered_set<pair<int, int>,PairHash> targetVisited;startStack.push({begina, beginb});targetStack.push({enda, endb});while (!startStack.empty() && !targetStack.empty()) {auto currentStart = startStack.top();auto currentTarget = targetStack.top();startStack.pop();targetStack.pop();startVisited.insert(currentStart);targetVisited.insert(currentTarget);// 检查是否相遇if (startVisited.count(currentTarget) || targetVisited.count(currentStart)) {return true;}// 处理邻居节点int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};for (auto dir : dirs) {int nextStartA = currentStart.first + dir[0];int nextStartB = currentStart.second + dir[1];if (nextStartA >= 0 && nextStartA < n && nextStartB >= 0 && nextStartB < m &&!startVisited.count({nextStartA, nextStartB})) {startStack.push({nextStartA, nextStartB});}int nextTargetA = currentTarget.first + dir[0];int nextTargetB = currentTarget.second + dir[1];if (nextTargetA >= 0 && nextTargetA < n && nextTargetB >= 0 && nextTargetB < m &&!targetVisited.count({nextTargetA, nextTargetB})) {targetStack.push({nextTargetA, nextTargetB});}}}return false;
}int main()
{cin>>n>>m;board=new char*[n];for(int i=0;i<n;i++){board[i]=new char[m];for(int j=0;j<m;j++) cin>>board[i][j];}showcurboard();return 0;
}

---

P1. b3625迷宫寻路 

#include <iostream>
#include <stack>
#include <unordered_set>
using namespace std;
int n,m;
char** board;
void showcurboard()
{for(int i=0;i<n;i++){for(int j=0;j<m;j++)cout<<board[i][j];cout<<endl;}
}
struct PairHash {template <class T1, class T2>std::size_t operator () (const std::pair<T1, T2> &pair) const {auto hash1 = std::hash<T1>{}(pair.first);auto hash2 = std::hash<T2>{}(pair.second);return hash1 ^ hash2;}
};
// 双向深度优先搜索函数
bool bidirectionalDFS(int begina, int beginb, int enda, int endb) {stack<pair<int, int>> startStack, targetStack;unordered_set<pair<int, int>,PairHash> startVisited;unordered_set<pair<int, int>,PairHash> targetVisited;startStack.push({begina, beginb});targetStack.push({enda, endb});while (!startStack.empty() && !targetStack.empty()) {auto currentStart = startStack.top();auto currentTarget = targetStack.top();startStack.pop();targetStack.pop();startVisited.insert(currentStart);targetVisited.insert(currentTarget);// 检查是否相遇if (startVisited.count(currentTarget) || targetVisited.count(currentStart)) {return true;}// 处理邻居节点int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};for (auto dir : dirs) {int nextStartA = currentStart.first + dir[0];int nextStartB = currentStart.second + dir[1];if (nextStartA >= 0 && nextStartA < n && nextStartB >= 0 && nextStartB < m &&!startVisited.count({nextStartA, nextStartB})&&board[nextStartA][nextStartB]=='.') {startStack.push({nextStartA, nextStartB});}int nextTargetA = currentTarget.first + dir[0];int nextTargetB = currentTarget.second + dir[1];if (nextTargetA >= 0 && nextTargetA < n && nextTargetB >= 0 && nextTargetB < m &&!targetVisited.count({nextTargetA, nextTargetB})&&board[nextTargetA][nextTargetB]=='.') {targetStack.push({nextTargetA, nextTargetB});}}}return false;
}int main()
{cin>>n>>m;board=new char*[n];for(int i=0;i<n;i++){board[i]=new char[m];for(int j=0;j<m;j++) cin>>board[i][j];}//showcurboard();bool ans=bidirectionalDFS(0,0,n-1,m-1);if(ans) cout<<"Yes";else cout<<"No";return 0;
}