使用邻接表存储表示,创建一个无向图G,分别进行深度优先搜索和广度优先搜索,请给出完整代码
时间: 2024-03-06 07:51:36 浏览: 68
好的,以下是使用邻接表存储表示的无向图G的深度优先搜索和广度优先搜索的完整代码。
```
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 图的邻接表存储结构
struct Graph {
int V; // 顶点数
vector<int> *adj; // 存储每个顶点的邻接表
};
// 创建一个新的图
Graph* createGraph(int V) {
Graph* graph = new Graph;
graph->V = V;
graph->adj = new vector<int>[V];
return graph;
}
// 添加一条边到图中
void addEdge(Graph* graph, int src, int dest) {
graph->adj[src].push_back(dest);
graph->adj[dest].push_back(src);
}
// 深度优先搜索
void DFS(Graph* graph, int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for (auto i = graph->adj[v].begin(); i != graph->adj[v].end(); i++) {
if (!visited[*i]) {
DFS(graph, *i, visited);
}
}
}
// 广度优先搜索
void BFS(Graph* graph, int v, bool visited[]) {
queue<int> q;
visited[v] = true;
q.push(v);
while (!q.empty()) {
v = q.front();
cout << v << " ";
q.pop();
for (auto i = graph->adj[v].begin(); i != graph->adj[v].end(); i++) {
if (!visited[*i]) {
visited[*i] = true;
q.push(*i);
}
}
}
}
int main() {
int V = 5; // 图的顶点数
Graph* graph = createGraph(V);
// 添加边
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
bool visited[V] = {false};
cout << "深度优先搜索结果:";
DFS(graph, 0, visited);
cout << endl;
for (int i = 0; i < V; i++) {
visited[i] = false;
}
cout << "广度优先搜索结果:";
BFS(graph, 0, visited);
cout << endl;
return 0;
}
```
注意,以上代码中的图是一个无向图,因此添加一条边时需要同时在两个顶点的邻接表中添加。另外,每个顶点的邻接表使用了C++ STL中的vector容器实现。
阅读全文