给出利用C++完成图的深度优先遍历算法、广度优先遍历算法的具体程序。要求是:其中,邻接表的创建相当于创建多个单链表。
时间: 2024-03-16 11:46:04 浏览: 83
C/C++实现图的深度优先遍历和广度优先遍历
好的,下面是C++实现图的深度优先遍历算法和广度优先遍历算法的代码示例,包括邻接表的创建过程。
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
//定义图的结构体
struct Graph {
int V; //顶点数
vector<int>* adj; //邻接表
};
//创建邻接表
void createGraph(Graph& g) {
cout << "请输入顶点数:";
cin >> g.V;
g.adj = new vector<int>[g.V]; //初始化邻接表
int u, v;
cout << "请输入边的起点和终点,以-1 -1结束:" << endl;
while (true) {
cin >> u >> v;
if (u == -1 && v == -1) {
break;
}
g.adj[u].push_back(v); //加入边
g.adj[v].push_back(u); //加入边,无向图需要加入两条边
}
}
//销毁邻接表
void destroyGraph(Graph& g) {
delete[] g.adj;
g.adj = nullptr;
}
//图的深度优先遍历
void DFS(Graph& g, vector<bool>& visited, int v) {
visited[v] = true;
cout << v << " ";
//遍历v的邻接点
for (auto u : g.adj[v]) {
if (!visited[u]) {
DFS(g, visited, u);
}
}
}
//图的广度优先遍历
void BFS(Graph& g, vector<bool>& visited, int v) {
queue<int> q;
visited[v] = true;
q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
//遍历u的邻接点
for (auto w : g.adj[u]) {
if (!visited[w]) {
visited[w] = true;
q.push(w);
}
}
}
}
int main() {
Graph g;
createGraph(g);
vector<bool> visited(g.V, false); //标记图的每个顶点是否被访问过
//从顶点0开始深度优先遍历
cout << "深度优先遍历:";
DFS(g, visited, 0);
cout << endl;
//从顶点0开始广度优先遍历
visited.assign(g.V, false); //重置visited数组
cout << "广度优先遍历:";
BFS(g, visited, 0);
cout << endl;
destroyGraph(g); //销毁邻接表
return 0;
}
```
以上代码实现了邻接表的创建和销毁,以及基于邻接表的深度优先遍历和广度优先遍历算法。
阅读全文