建立一个图的邻接表,再实现恩的深度优先遍历序列。具体如下:編写一个程序,定义恩的邻接表存储结构并创建无向图的邻接表,在此基础上对无向图进行深度优先遍历,最后在主西数中进行调用演示。
时间: 2024-05-16 08:16:17 浏览: 14
好的,我可以帮你实现这个问题。
首先,让我们定义恩的邻接表存储结构。我们可以使用一个链表来存储每个顶点的邻居节点。具体代码如下:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 定义邻接表节点
struct ListNode {
int val;
ListNode* next;
ListNode(int _val) : val(_val), next(nullptr) {}
};
// 定义邻接表
class AdjacencyList {
public:
int n; // 图的顶点数
vector<ListNode*> adj; // 存储邻接表
AdjacencyList(int _n) : n(_n), adj(n) {}
// 添加无向边
void addEdge(int u, int v) {
ListNode* node = new ListNode(v);
node->next = adj[u];
adj[u] = node;
node = new ListNode(u);
node->next = adj[v];
adj[v] = node;
}
};
```
接下来,我们可以使用递归的方式对无向图进行深度优先遍历。具体代码如下:
```c++
class DFS {
public:
vector<bool> visited;
vector<int> res; // 存储遍历序列
DFS(int n) : visited(n, false) {}
void dfs(AdjacencyList& graph, int u) {
visited[u] = true;
res.push_back(u);
for (ListNode* p = graph.adj[u]; p; p = p->next) {
int v = p->val;
if (!visited[v]) {
dfs(graph, v);
}
}
}
};
```
最后,我们可以在主函数中创建无向图的邻接表,并调用深度优先遍历算法进行遍历。具体代码如下:
```c++
int main() {
// 创建无向图的邻接表
AdjacencyList graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(2, 4);
// 对无向图进行深度优先遍历
DFS dfs(graph.n);
dfs.dfs(graph, 0);
// 输出遍历序列
for (int i = 0; i < dfs.res.size(); i++) {
cout << dfs.res[i] << " ";
}
cout << endl;
return 0;
}
```
以上代码实现了恩的邻接表存储结构和深度优先遍历算法,并且在主函数中进行了演示。你可以根据自己的需要修改顶点数量、添加边等操作,来应用到自己的问题中。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)