基于邻接表的深度优先遍历代码
时间: 2023-07-24 19:13:49 浏览: 62
以下是基于邻接表的深度优先遍历代码(C++实现):
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100; // 最大顶点个数
vector<int> adj[MAXN]; // 邻接表存图
bool vis[MAXN]; // 标记数组,标记每个顶点是否已访问
void dfs(int u) { // 深度优先遍历函数
vis[u] = true; // 标记当前顶点已访问
cout << u << " "; // 输出当前顶点
for (int i = 0; i < adj[u].size(); i++) { // 遍历所有邻接点
int v = adj[u][i];
if (!vis[v]) { // 如果未访问,则递归访问
dfs(v);
}
}
}
int main() {
int n, m; // n表示顶点个数,m表示边数
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v); // 存储边
adj[v].push_back(u); // 无向图需要存储反向边
}
for (int i = 1; i <= n; i++) { // 按顺序遍历每个顶点
if (!vis[i]) { // 如果未访问,则以该顶点为起点开始遍历
dfs(i);
}
}
return 0;
}
```
其中,`adj`为邻接表,`vis`为标记数组,`dfs`为深度优先遍历函数。主函数中按顺序遍历每个顶点,如果未访问,则以该顶点为起点开始遍历。在深度优先遍历函数中,先标记当前顶点已访问,然后输出当前顶点,最后遍历所有邻接点,如果未访问,则递归访问。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)