有向图遍历用cpp实现
时间: 2023-07-12 16:50:43 浏览: 40
以下是使用C++实现有向图的深度优先搜索(DFS)遍历的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
visited[node] = true;
cout << node << " ";
for (int i = 0; i < graph[node].size(); i++) {
int next_node = graph[node][i];
if (!visited[next_node]) {
dfs(graph, visited, next_node);
}
}
}
int main() {
int n, m; // n为顶点个数,m为边数
cin >> n >> m;
vector<vector<int>> graph(n);
vector<bool> visited(n, false);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v); // 添加边
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(graph, visited, i);
}
}
return 0;
}
```
输入格式为:第一行包含两个整数n和m,表示有向图的顶点个数和边数。接下来m行每行包含两个整数u和v,表示从顶点u到顶点v有一条有向边。输出为有向图的深度优先遍历结果。