用c++代码写出bf算法
时间: 2024-10-20 17:02:04 浏览: 24
BF(Breadth-First Search,广度优先搜索)是一种用于遍历或查找图的算法,它按照层级顺序逐层探索节点。在C++中,我们可以使用队列数据结构来实现这个算法。以下是一个简单的BF算法的示例,假设我们有一个邻接列表表示的无向图:
```cpp
#include <iostream>
#include <list>
#include <queue>
using namespace std;
// 定义图节点
struct Node {
int value;
list<Node*> neighbors;
};
// 检查图是否包含目标值
bool search(Node* start, int target) {
queue<Node*> q; // 初始化队列
q.push(start); // 将起始节点入队
while (!q.empty()) {
Node* curr = q.front(); // 取出队首节点
q.pop();
if (curr->value == target) { // 如果找到目标值
return true;
}
for (Node* neighbor : curr->neighbors) { // 遍历邻居
q.push(neighbor);
}
}
return false; // 没有找到目标,返回false
}
int main() {
// 创建并初始化你的图...
Node start_node = {5, {2, 8, 9}};
Node node_2 = {2, {1, 4, 7}};
Node node_8 = {8, {6, 0}};
// ... 等等
bool found = search(&start_node, 8); // 搜索8
if (found)
cout << "Target value found." << endl;
else
cout << "Target value not found." << endl;
return 0;
}
```
在这个例子中,`search`函数会从给定的起始节点开始,然后对每个相邻节点进行深度优先遍历,直到找到目标值或者遍历完整个图。如果找不到目标值,则返回`false`。
阅读全文