c++实现广度优先搜索
时间: 2024-01-25 09:12:08 浏览: 29
以下是使用C++实现广度优先搜索的示例代码:
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 定义图的节点结构
struct Node {
int value;
vector<Node*> neighbors;
};
// 广度优先搜索函数
void BFS(Node* start) {
queue<Node*> q;
vector<bool> visited;
// 初始化visited数组,标记所有节点为未访问
for (int i = 0; i < 100; i++) {
visited.push_back(false);
}
// 将起始节点加入队列并标记为已访问
q.push(start);
visited[start->value] = true;
while (!q.empty()) {
Node* current = q.front();
q.pop();
// 输出当前节点的值
cout << current->value << " ";
// 遍历当前节点的邻居节点
for (Node* neighbor : current->neighbors) {
// 如果邻居节点未被访问,则将其加入队列并标记为已访问
if (!visited[neighbor->value]) {
q.push(neighbor);
visited[neighbor->value] = true;
}
}
}
}
int main() {
// 构建示例的图
Node* node0 = new Node{0};
Node* node1 = new Node{1};
Node* node2 = new Node{2};
Node* node3 = new Node{3};
Node* node4 = new Node{4};
node0->neighbors.push_back(node1);
node0->neighbors.push_back(node2);
node1->neighbors.push_back(node3);
node2->neighbors.push_back(node3);
node2->neighbors.push_back(node4);
node3->neighbors.push_back(node4);
// 执行广度优先搜索
BFS(node0);
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)