用C++完整写出以下程序。对给定的以邻接表为存储结构的图,实现连通无向图的深度优先遍历和广度优先遍历算法。以用户指定的结点为起点,分别输出两种遍历下的结点访问序列。
时间: 2024-12-15 14:13:40 浏览: 22
在C++中,我们可以使用`vector`来表示邻接表,`stack`和`queue`分别用于深度优先搜索(DFS)和广度优先搜索(BFS)。这里给出一个简单的实现:
```cpp
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
// 图节点类
class GraphNode {
public:
int data;
vector<GraphNode*> adj; // 邻接列表
GraphNode(int val) : data(val) {}
};
// 深度优先遍历
void dfs(GraphNode* node, vector<bool>& visited) {
if (node == nullptr || visited[node->data])
return;
cout << node->data << " "; // 访问节点
visited[node->data] = true;
for (GraphNode* neighbor : node->adj) {
dfs(neighbor, visited);
}
}
// 广度优先遍历
void bfs(GraphNode* root, vector<bool>& visited) {
queue<GraphNode*> q;
q.push(root);
visited[root->data] = true;
while (!q.empty()) {
GraphNode* node = q.front();
cout << node->data << " "; // 访问节点
q.pop();
for (GraphNode* neighbor : node->adj) {
if (!visited[neighbor->data]) {
visited[neighbor->data] = true;
q.push(neighbor);
}
}
}
}
int main() {
// 初始化图
// ... (省略创建图的具体实现)
// 用户指定的起始节点
int startNode;
cin >> startNode;
vector<bool> visited(graph.size(), false); // 初始时所有节点未访问
cout << "Depth First Search from node " << startNode << ": ";
dfs(find(startNode), visited);
cout << "\n\n Breadth First Search from node " << startNode << ": ";
bfs(find(startNode), visited);
return 0;
}
```
这个程序首先定义了一个`GraphNode`类,然后实现了`dfs`和`bfs`函数来进行遍历。在`main`函数中,用户输入开始节点,然后调用这两个函数并打印结果。
注意,`find(startNode)`是一个假设,你需要提供一个实际查找特定节点的方法,这取决于你的邻接表是如何组织的(例如,如果你使用数组索引来存储邻居,你可以直接使用那个索引;如果是链表,可能需要遍历整个链表找到目标节点)。
阅读全文