在 BFS 实现中,由于迭代器引用无效而发生崩溃
// // Created by wuxianggujun on 2025/4/7. // #include #include <unordered_map> #include #include #include #include <unordered_set>
using std::cout; using std::endl;
// Check if the name ends with 'm', indicating a mango seller bool is_seller(const std::string& name) { return !name.empty() && name.back() == 'm'; }
template bool search(const T& name, const std::unordered_map<T, std::vector>& graph) { std::queue search_queue; std::unordered_set searched;
// Key fix 1: check if the start node exists
auto start_it = graph.find(name);
if (start_it == graph.end()) {
cout << "Start node not found in graph!" << endl;
return false;
}
// Initialize the queue
for (const auto& friend_name : start_it->second) {
search_queue.push(friend_name);
}
while (!search_queue.empty()) {
// Key fix 2: use value copy instead of reference
T person = search_queue.front();
search_queue.pop();
if (searched.count(person)) continue;
if (is_seller(person)) {
cout << person << " is a mango seller." << endl;
return true;
}
// Key fix 3: check if the associated node exists
auto person_it = graph.find(person);
if (person_it != graph.end()) {
for (const auto& friend_name : person_it->second) {
search_queue.push(friend_name);
}
}
searched.insert(person);
}
cout << "No mango seller found." << endl;
return false;
}
int main() { std::unordered_map<std::string, std::vectorstd::string> graph; graph.insert({"you", {"alice", "bob", "claire"}}); graph.insert({"bob", {"anuj", "peggy"}}); graph.insert({"alice", {"peggy"}}); graph.insert({"claire", {"thom", "jonny"}}); graph.insert({"anuj", {}}); graph.insert({"peggy", {}}); graph.insert({"thom", {}}); graph.insert({"jonny", {}});
std::string name = "you";
bool result = search(name, graph);
cout << "Found mango seller: " << result << endl;
}
内容来源: egonSchiele/grokking_algorithms