用c++写一个图,实现深度优先和广度优先
时间: 2024-03-04 22:49:24 浏览: 18
好的,下面是一个基本的图的C++实现,同时也包含了深度优先搜索(DFS)和广度优先搜索(BFS)的实现:
```C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 定义图节点结构体
struct GraphNode {
int val;
vector<GraphNode*> neighbors;
GraphNode(int _val) : val(_val) {}
};
// 深度优先搜索
void DFS(GraphNode* node, vector<bool>& visited) {
visited[node->val] = true;
cout << node->val << " ";
for (auto neighbor : node->neighbors) {
if (!visited[neighbor->val]) {
DFS(neighbor, visited);
}
}
}
// 广度优先搜索
void BFS(GraphNode* node, vector<bool>& visited) {
queue<GraphNode*> q;
q.push(node);
visited[node->val] = true;
while (!q.empty()) {
GraphNode* cur = q.front();
q.pop();
cout << cur->val << " ";
for (auto neighbor : cur->neighbors) {
if (!visited[neighbor->val]) {
visited[neighbor->val] = true;
q.push(neighbor);
}
}
}
}
int main() {
// 构造图
vector<GraphNode*> graph(5);
for (int i = 0; i < 5; i++) {
graph[i] = new GraphNode(i);
}
graph[0]->neighbors.push_back(graph[1]);
graph[0]->neighbors.push_back(graph[2]);
graph[1]->neighbors.push_back(graph[3]);
graph[2]->neighbors.push_back(graph[3]);
graph[3]->neighbors.push_back(graph[4]);
// 遍历图
vector<bool> visited(5, false);
cout << "DFS: ";
DFS(graph[0], visited);
cout << endl;
visited.assign(5, false);
cout << "BFS: ";
BFS(graph[0], visited);
cout << endl;
return 0;
}
```
输出结果为:
```
DFS: 0 1 3 4 2
BFS: 0 1 2 3 4
```
希望这个例子能够帮助你理解图和搜索的基本实现。