对所给邻接表进行广度遍历用c++表示,函数将邻接表进行广度遍历
时间: 2023-06-16 13:07:29 浏览: 84
C++实现图的邻接表的广度优先遍历
5星 · 资源好评率100%
下面是一个用C++实现的邻接表广度遍历的函数:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 邻接表节点
struct AdjListNode {
int dest;
AdjListNode* next;
};
// 邻接表
struct AdjList {
AdjListNode* head;
};
// 图
class Graph {
private:
int V; // 顶点数
vector<AdjList> adj; // 邻接表
public:
Graph(int V) {
this->V = V;
adj.resize(V);
for (int i = 0; i < V; ++i) {
adj[i].head = nullptr;
}
}
// 添加边
void addEdge(int u, int v) {
AdjListNode* node = new AdjListNode{v, nullptr};
if (adj[u].head == nullptr) {
adj[u].head = node;
} else {
AdjListNode* curr = adj[u].head;
while (curr->next != nullptr) {
curr = curr->next;
}
curr->next = node;
}
}
// 广度遍历
void BFS(int s) {
vector<bool> visited(V, false); // 标记是否访问过
queue<int> q; // 使用队列辅助遍历
visited[s] = true;
q.push(s);
while (!q.empty()) {
int u = q.front();
cout << u << " ";
q.pop();
AdjListNode* curr = adj[u].head;
while (curr != nullptr) {
int v = curr->dest;
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
curr = curr->next;
}
}
}
};
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);
cout << endl;
return 0;
}
```
这里实现了一个邻接表数据结构,并且提供了添加边和广度遍历的功能。在主函数中创建了一个图对象,并添加了一些边,然后从顶点2开始进行广度遍历。
阅读全文