图广度优先遍历递归算法
时间: 2023-10-20 21:05:59 浏览: 53
图广度优先遍历通常使用队列来实现,不需要使用递归算法。下面是图广度优先遍历的非递归算法实现:
```
void BFS(int start, int n, vector<vector<int>> &graph) {
vector<bool> visited(n, false); // 记录节点是否已经访问过
queue<int> q;
q.push(start); // 将起始节点加入队列
visited[start] = true; // 标记起始节点为已访问
while (!q.empty()) {
int node = q.front(); // 取出队列的头部节点
q.pop();
// 遍历当前节点的所有邻接节点
for (int i = 0; i < graph[node].size(); i++) {
int neighbor = graph[node][i];
if (!visited[neighbor]) { // 如果邻接节点未被访问
q.push(neighbor); // 将邻接节点加入队列
visited[neighbor] = true; // 标记邻接节点为已访问
}
}
}
}
```
其中,`start` 表示起始节点的编号,`n` 表示节点总数,`graph` 是一个邻接表,表示图中节点之间的连接关系。 `visited` 数组用于记录节点是否已经被访问过,初始化为 `false`。队列 `q` 用于存储待访问的节点。算法的时间复杂度为 $O(n+m)$,其中 $m$ 是边的数量。
相关推荐
![](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)