//--------------------用邻接表实现无向图的深度优先遍历和广度优先遍历算法------------------------------------ #include <stdio.
时间: 2024-06-08 11:03:51 浏览: 19
在C++中,使用邻接表(Adjacency List)实现无向图的深度优先遍历(Depth-First Search, DFS)和广度优先遍历(Breadth-First Search, BFS)是常见的图数据结构操作。这里是一个简单的概述:
**深度优先遍历(DFS):**
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 图节点结构体
struct Node {
int id;
vector<int> neighbors; // 邻接表中的邻居节点
};
void dfs(Node* node, vector<bool>& visited) {
visited[node->id] = true; // 标记当前节点已访问
cout << node->id << " "; // 访问并打印节点
// 遍历邻接表
for (int neighbor : node->neighbors) {
if (!visited[neighbor]) {
dfs(&graph[neighbor], visited); // 递归访问未访问的邻居
}
}
}
// 假设 graph 是邻接表表示的无向图
void dfsTraversal(Node* start) {
vector<bool> visited(graph.size(), false);
dfs(start, visited);
}
```
**广度优先遍历(BFS):**
```cpp
#include <queue>
void bfs(Node* node, vector<bool>& visited) {
queue<Node*> q;
q.push(node);
while (!q.empty()) {
Node* current = q.front();
q.pop();
visited[current->id] = true;
for (int neighbor : current->neighbors) {
if (!visited[neighbor]) {
cout << neighbor << " ";
q.push(&graph[neighbor]);
}
}
}
}
void bfsTraversal(Node* start) {
vector<bool> visited(graph.size(), false);
bfs(start, visited);
}
```