编写一个c++编程,使用深度优先遍历的方式遍历一个无向图,并输出遍历序列,要求使用邻接表存储无向图。
时间: 2024-12-26 12:29:12 浏览: 17
在C++中,使用深度优先搜索(Depth First Search,DFS)遍历无向图并输出遍历序列,通常会采用递归的方式来实现。由于采用了邻接表(Adjacency List)作为图的数据结构,可以更高效地处理节点间的连接。
下面是一个基本的C++程序示例:
```cpp
#include <iostream>
#include <vector>
// 邻接列表表示图的数据结构
struct Node {
int value;
std::vector<int> neighbors; // 存储相邻节点的索引
};
// 用于标记节点是否已被访问过
bool visited[100];
// 深度优先遍历函数
void dfs(Node* node, std::string& traversal_sequence) {
if (node == nullptr || visited[node->value]) return;
visited[node->value] = true;
traversal_sequence += std::to_string(node->value) + " "; // 将当前节点添加到序列
for (int neighbor : node->neighbors) {
dfs(graph[neighbor], traversal_sequence); // 对未访问的邻居递归调用dfs
}
}
int main() {
// 假设我们有一个包含5个节点的无向图,用邻接表表示,这里仅列出部分数据
Node graph[] = { {1, {2}}, {2, {1, 3}}, {3, {2, 4}}, {4, {3, 5}}, {5, {4}} };
int num_nodes = sizeof(graph) / sizeof(graph[0]);
std::string sequence;
dfs(graph[0], sequence);
std::cout << "Depth-first search traversal sequence: " << sequence << std::endl;
return 0;
}
```
在这个例子中,`graph`数组代表了邻接表,每个元素代表一个节点,其值和邻居的索引构成邻接列表。`dfs`函数从给定的起始节点开始,逐个访问相邻节点,直到所有路径都被探索完毕。
阅读全文