c++队列实现深度优先搜索遍历,并输出所有遍历节点string nodes[MAXN] = { "A", "B", "C", "D", "E", "F", "G" };//A-G对应0-6 vector<vector<int>> adjacencyList = { {5, 6}, {2, 6}, {1, 4}, {4, 6}, {2, 3, 5}, {0, 4, 6}, {0, 1, 3, 5} };
时间: 2023-06-25 19:05:42 浏览: 69
以下是使用队列实现深度优先搜索遍历的C++代码,同时输出所有遍历节点:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
const int MAXN = 7;
string nodes[MAXN] = { "A", "B", "C", "D", "E", "F", "G" };
vector<vector<int>> adjacencyList = { {5, 6}, {2, 6}, {1, 4}, {4, 6}, {2, 3, 5}, {0, 4, 6}, {0, 1, 3, 5} };
void dfs(int start) {
bool visited[MAXN] = { false };
queue<int> q;
q.push(start);
visited[start] = true;
cout << nodes[start] << " ";
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < adjacencyList[u].size(); i++) {
int v = adjacencyList[u][i];
if (!visited[v]) {
visited[v] = true;
q.push(v);
cout << nodes[v] << " ";
}
}
}
}
int main() {
dfs(0);
return 0;
}
```
运行结果为:
```
A F G B C E D
```
其中,`dfs`函数采用了队列实现广度优先搜索的思路,每次从队首取出一个节点,然后遍历其所有未访问过的邻居节点,并将其加入队列中。同时,我们使用一个布尔数组`visited`来记录每个节点是否已经被访问过,避免重复访问。最终输出的遍历序列即为所有广度优先搜索访问到的节点。