中国水电建设招标网站,wordpress官方的三个主题好排名,福州百度快照优化,iapp网站怎么做软件双向深度优先搜索#xff08;Bidirectional Depth-First Search#xff09;是一种图搜索算法#xff0c;旨在通过从起始节点和目标节点同时开始#xff0c;沿着深度优先搜索的路径向前探索#xff0c;以减少搜索空间并提高搜索效率。
1. 基本原理
双向深度优先搜索同时从…双向深度优先搜索Bidirectional Depth-First Search是一种图搜索算法旨在通过从起始节点和目标节点同时开始沿着深度优先搜索的路径向前探索以减少搜索空间并提高搜索效率。
1. 基本原理
双向深度优先搜索同时从起始节点和目标节点开始搜索通过交替地在两个方向上进行深度优先搜索直到两个搜索路径相遇。
2. 算法步骤
初始化两个空的栈一个用于从起始节点开始的搜索另一个用于从目标节点开始的搜索。将起始节点和目标节点分别推入两个栈。从两个栈中分别出栈一个节点进行如下操作 标记节点为已访问。检查当前节点是否在两个搜索方向上相遇如果相遇则搜索结束。否则对当前节点的未访问邻居节点进行处理 对于起始节点搜索方向将未访问的邻居节点推入起始栈。对于目标节点搜索方向将未访问的邻居节点推入目标栈。重复步骤3直到两个栈中的节点相遇或者两个栈都为空。
3. 优缺点
优点 相较于单向深度优先搜索双向深度优先搜索在搜索空间较大时能够更快地找到目标节点。缺点 需要额外的内存空间来维护两个搜索方向的栈。在特定情况下可能会比单向搜索更慢例如在目标节点附近的情况。
代码示例邻接表表示的图
#include iostream
#include vector
#include stack
#include unordered_setusing namespace std;// 无权图的邻接表表示
vectorvectorint graph;// 双向深度优先搜索函数
bool bidirectionalDFS(int start, int target) {stackint startStack, targetStack;unordered_setint 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_mapcount函数会返回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 i0;in;i){for(int j0;jm;j)coutboard[i][j];coutendl;}
}
struct PairHash {template class T1, class T2std::size_t operator () (const std::pairT1, T2 pair) const {auto hash1 std::hashT1{}(pair.first);auto hash2 std::hashT2{}(pair.second);return hash1 ^ hash2;}
};
// 双向深度优先搜索函数
bool bidirectionalDFS(int begina, int beginb, int enda, int endb) {stackpairint, int startStack, targetStack;unordered_setpairint, int,PairHash startVisited;unordered_setpairint, 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()
{cinnm;boardnew char*[n];for(int i0;in;i){board[i]new char[m];for(int j0;jm;j) cinboard[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 i0;in;i){for(int j0;jm;j)coutboard[i][j];coutendl;}
}
struct PairHash {template class T1, class T2std::size_t operator () (const std::pairT1, T2 pair) const {auto hash1 std::hashT1{}(pair.first);auto hash2 std::hashT2{}(pair.second);return hash1 ^ hash2;}
};
// 双向深度优先搜索函数
bool bidirectionalDFS(int begina, int beginb, int enda, int endb) {stackpairint, int startStack, targetStack;unordered_setpairint, int,PairHash startVisited;unordered_setpairint, 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()
{cinnm;boardnew char*[n];for(int i0;in;i){board[i]new char[m];for(int j0;jm;j) cinboard[i][j];}//showcurboard();bool ansbidirectionalDFS(0,0,n-1,m-1);if(ans) coutYes;else coutNo;return 0;
}
