突发奇想
2024-08-20 22:49:15
发布于：广东
39阅读
0回复
0点赞
用两个stack写广搜
#include <bits/stdc++.h>
using namespace std;
class StackBFS {
public:
void eq(const int& item) {
s1.push(item);
}
int dq() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
int top = s2.top();
s2.pop();
return top;
}
bool is_empty() const {
return s1.empty() && s2.empty();
}
private:
stack<int> s1; //一个进
stack<int> s2; //一个出
//用stack来模拟queue-_-我可真是个小天才
};
void bfs(const vector<vector<int>>& e, int start) {
StackBFS queue;
set<int> vis;
queue.eq(start);
vis.insert(start);
while (!queue.is_empty()) {
int node = queue.dq();
cout << node << " ";
for (const int& neighbor : e[node]) {
if (vis.find(neighbor) == vis.end()) {
vis.insert(neighbor);
queue.eq(neighbor);
}
}
}
}
int main() {
vector<vector<int>>e={
{1, 1},
{4,5, 1},
{4, 5},
{4},
{1, 8}, //恶臭数字
{8, 8}
};
bfs(e, 0);
return 0;
}
有帮助，赞一个