用C++完成图的深度优先遍历算法、广度优先遍历算法。其中,邻接表的创建相当于创建多个单链表。
时间: 2024-02-21 11:59:36 浏览: 73
好的,我可以回答你的问题。
首先,我们需要定义一个表示图的数据结构,这里我们使用邻接表来表示图。邻接表由若干个单链表组成,每个单链表表示一个顶点的所有邻接点。邻接表的创建包括两个步骤:
1. 定义一个结构体表示图的顶点,包括顶点的编号和指向第一个邻接点的指针。
2. 创建邻接表,对于每个顶点,创建一个单链表表示它的邻接点。
下面是具体的代码实现:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 定义图的顶点结构体
struct Vertex {
int num; // 顶点编号
struct Node* next; // 指向第一个邻接点的指针
};
// 定义邻接点结构体
struct Node {
int num; // 邻接点编号
struct Node* next; // 指向下一个邻接点的指针
};
// 创建邻接表
vector<Vertex> createGraph(int n, vector<vector<int>>& edges) {
vector<Vertex> graph(n);
for (int i = 0; i < n; ++i) {
graph[i].num = i;
graph[i].next = nullptr;
}
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
Node* node = new Node{v, graph[u].next};
graph[u].next = node;
node = new Node{u, graph[v].next};
graph[v].next = node;
}
return graph;
}
```
接下来是深度优先遍历算法的实现:
```c++
// 深度优先遍历
void dfs(vector<Vertex>& graph, int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
Node* node = graph[v].next;
while (node) {
if (!visited[node->num]) {
dfs(graph, node->num, visited);
}
node = node->next;
}
}
```
深度优先遍历算法的核心是递归遍历每个邻接点,对于每个未被访问过的邻接点,继续递归遍历。
最后是广度优先遍历算法的实现:
```c++
// 广度优先遍历
void bfs(vector<Vertex>& graph, int v, vector<bool>& visited) {
queue<int> q;
q.push(v);
visited[v] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
Node* node = graph[u].next;
while (node) {
if (!visited[node->num]) {
q.push(node->num);
visited[node->num] = true;
}
node = node->next;
}
}
}
```
广度优先遍历算法的核心是使用队列来存储待访问的顶点,对于每个已经访问过的顶点,遍历它的所有邻接点,并将未访问过的顶点加入队列。
完整代码如下:
阅读全文