有向图的邻接表的DFS
时间: 2023-11-05 19:00:11 浏览: 42
邻接表表示的有向图的深度优先遍历可以使用递归方式实现。具体步骤如下:
1. 初始化所有顶点的访问标记为false。
2. 从任意一个未被访问的顶点开始,对该顶点进行深度优先遍历。
3. 对于当前访问的顶点v,将其访问标记设为true。
4. 遍历该顶点的所有邻接点,如果邻接点未被访问,则递归访问该邻接点。
5. 如果所有邻接点都已被访问,返回上一级顶点。
6. 重复步骤4和5,直到所有顶点都被访问过。
下面是一个基于邻接表的深度优先遍历的实现代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
void DFS(vector<int> adj[], int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i];
if (!visited[u]) {
DFS(adj, u, visited);
}
}
}
void DFS(vector<int> adj[], int num_vertices) {
bool visited[num_vertices];
for (int i = 0; i < num_vertices; i++) {
visited[i] = false;
}
for (int i = 0; i < num_vertices; i++) {
if (!visited[i]) {
DFS(adj, i, visited);
}
}
}
int main() {
int num_vertices = 5;
vector<int> adj[num_vertices];
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(2);
adj[2].push_back(0);
adj[2].push_back(3);
adj[3].push_back(3);
adj[4].push_back(4);
DFS(adj, num_vertices);
return 0;
}
```
这里的adj是邻接表,num_vertices是顶点总数,DFS函数有两个版本,一个是从某个顶点开始遍历,另一个是对整个图进行遍历。