用c++语言写一个关于用数组的广度优先遍历的函数
时间: 2024-02-12 13:03:44 浏览: 17
好的,这里是一个用数组的C++实现广度优先遍历的函数:
```c++
#include <iostream>
#include <queue>
using namespace std;
// 定义一个图结构
class Graph {
private:
int** adjMatrix; // 邻接矩阵
int numVertices; // 图中节点的数量
public:
// 构造函数
Graph(int numVertices) {
this->numVertices = numVertices;
adjMatrix = new int*[numVertices];
for (int i = 0; i < numVertices; i++) {
adjMatrix[i] = new int[numVertices];
for (int j = 0; j < numVertices; j++) {
adjMatrix[i][j] = 0;
}
}
}
// 添加边
void addEdge(int u, int v) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1;
}
// 广度优先遍历
void BFS(int startVertex) {
bool* visited = new bool[numVertices] { false }; // 用于标记是否访问过
queue<int> q;
visited[startVertex] = true;
q.push(startVertex);
while (!q.empty()) {
int curVertex = q.front();
cout << curVertex << " ";
q.pop();
for (int adjVertex = 0; adjVertex < numVertices; adjVertex++) {
if (adjMatrix[curVertex][adjVertex] == 1 && !visited[adjVertex]) {
visited[adjVertex] = true;
q.push(adjVertex);
}
}
}
}
};
// 测试 BFS 函数
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "BFS(starting from vertex 2): ";
g.BFS(2);
return 0;
}
```
这个函数使用了一个 `queue` 来存储待遍历的节点,使用了一个 `bool` 数组来标记每个节点是否已经被访问过。在遍历过程中,我们从队列中取出一个节点,遍历它的所有邻居节点,将未访问过的邻居节点加入队列中。重复这个过程直到队列为空。
注意,在这个实现中,我们使用了邻接矩阵来表示图结构,而不是邻接表。