bfs广度优先搜索c++
时间: 2023-11-11 08:58:46 浏览: 121
广度优先查找 BFS
广度优先搜索(BFS)是一种图形搜索算法,用于遍历或搜索树或图的数据结构。它从根节点开始,逐层遍历整个图,直到找到目标节点或遍历完整个图。
以下是C++中BFS的基本实现:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void bfs(vector<vector<int>>& graph, int start) {
queue<int> q;
vector<bool> visited(graph.size(), false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int curr = q.front();
q.pop();
cout << curr << " ";
for (int i = 0; i < graph[curr].size(); i++) {
int neighbor = graph[curr][i];
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
}
int main() {
vector<vector<int>> graph = {{1, 2}, {0, 2, 3}, {0, 1, 3}, {1, 2}};
bfs(graph, 0);
return 0;
}
```
输出结果为:0 1 2 3
阅读全文