赞
踩
双向BFS(Bidirectional Breadth-First Search)是一种图搜索算法,它从图的两端同时开始搜索,直到两个搜索相遇。其基本思想是从起始点和目标点同时进行BFS搜索,直到两个搜索相遇为止,这个相遇的点就是起始点和目标点之间的最短路径。
双向BFS的搜索过程如下:
初始化起始点和目标点,将它们分别放入起点队列和目标点队列中。
从起点队列和目标点队列中分别取出一个点,分别进行扩展操作。比如,从起点队列中取出一个点,遍历它的所有邻居节点,将未被访问的邻居节点加入到起点队列中,并记录它们的深度(或距离)。
同样地,从目标点队列中取出一个点,遍历它的所有邻居节点,将未被访问的邻居节点加入到目标点队列中,并记录它们的深度(或距离)。
检查起点队列和目标点队列中的节点是否相遇。如果相遇,说明已经找到了起点和目标点之间的最短路径。此时可以停止搜索并返回最短路径。
如果起点队列和目标点队列中的节点没有相遇,继续从两个队列中取出节点进行扩展操作,直到相遇为止。
双向BFS通常可以比传统的BFS更快地找到最短路径,因为它可以同时从起点和目标点进行搜索,从而减少搜索空间。同时,双向BFS还需要使用两个队列来存储搜索过程中的节点,因此需要更多的空间。
class Solution { public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { //预处理 if(find(wordList.begin(),wordList.end(),endWord)==wordList.end()) return 0; if(find(wordList.begin(),wordList.end(),beginWord)==wordList.end()) wordList.push_back(beginWord); queue<string>bq,eq; unordered_set<string>check1,check2; int n1=1,n2=1;//记录搜索层数 check1.insert(beginWord); check2.insert(endWord); bq.push(beginWord); eq.push(endWord); while(!bq.empty()&&!eq.empty()) { if(bq.size()>eq.size())//交替bfs { if(bfs(eq,check2,check1,wordList)) return n1+n2; n2++; } else { if(bfs(bq,check1,check2,wordList)) return n1+n2; n1++; } } return 0; } //遍历一层 bool bfs(queue<string>&q,unordered_set<string>&q_check,unordered_set<string>&t_check,vector<string>&wordList) //q表示要bfs的队列,q_check表示改队列对应的哈希,t_check表示相反方向的bfs对应的哈希 { int sum=q.size(); while(sum--) { for(auto &a:wordList)// 遍历词典 { if(q_check.find(a)!=q_check.end()) //如果访问过 continue; if(ifturn(q.front(),a)) // 如果能转化 { if(t_check.find(a)!=t_check.end()) // 如果另一侧已经访问过了 return true; else { q.push(a);//将q.front()的邻接点入栈 q_check.insert(a); } } } q.pop(); } return false; } bool ifturn(string&a,string&b)//判断能否转化 { int dif=0; for(int i=0;i<a.size();i++) { if(a[i]!=b[i]) dif++; } return dif==1; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。