用c++实现图的深度优先遍历

以下是使用C++实现图的深度优先遍历的代码示例：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 100; // 最大节点数
vector<int> G[MAXN]; // 图的邻接表表示
bool visited[MAXN]; // 记录每个节点是否被访问过

// 递归实现深度优先遍历
void dfs(int u) {
    visited[u] = true;
    cout << u << " "; // 输出遍历到的节点
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!visited[v]) {
            dfs(v);
        }
    }
}

// 非递归实现深度优先遍历
void dfs2(int u) {
    stack<int> s;
    s.push(u);
    visited[u] = true;
    cout << u << " "; // 输出遍历到的节点
    while (!s.empty()) {
        int u = s.top();
        s.pop();
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            if (!visited[v]) {
                visited[v] = true;
                cout << v << " "; // 输出遍历到的节点
                s.push(v);
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数和边数
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入一条边的两个端点
        G[u].push_back(v);
        G[v].push_back(u); // 无向图需要加上这一行
    }
    // 从节点1开始深度优先遍历
    dfs(1);
    cout << endl;
    // 初始化visited数组
    fill(visited, visited + MAXN, false);
    // 从节点1开始深度优先遍历
    dfs2(1);
    cout << endl;
    return 0;
}