深度优先搜索遍历c++语言代码

深度优先搜索（DFS）是一种常用的图遍历算法，其基本思想是从图的某个起始顶点出发，沿着一条路走到底，直到不能再走为止，然后返回上一个节点，从该节点继续走其他的路径，直到所有的路径都被遍历为止。在实现过程中，可以使用递归或者栈来保存遍历过程中的状态。

以下是深度优先搜索遍历C++语言代码的示例：

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

void dfs(vector<vector<int>>& graph, int start, vector<bool>& visited) {
    visited[start] = true; // 标记起始节点已经被访问
    cout << start << " "; // 输出遍历到的节点
    for (int i = 0; i < graph[start].size(); i++) { // 遍历起始节点的邻接节点
        int next = graph[start][i];
        if (!visited[next]) { // 如果邻接节点没有被访问过，则递归访问该节点
            dfs(graph, next, visited);
        }
    }
}

void dfs_iterative(vector<vector<int>>& graph, int start, vector<bool>& visited) {
    stack<int> st;
    st.push(start); // 将起始节点压入栈中
    visited[start] = true; // 标记起始节点已经被访问
    cout << start << " "; // 输出遍历到的节点
    while (!st.empty()) {
        int cur = st.top();
        bool has_unvisited = false; // 标记当前节点是否有未访问的邻接节点
        for (int i = 0; i < graph[cur].size(); i++) {
            int next = graph[cur][i];
            if (!visited[next]) { // 如果有未访问的邻接节点，则将其压入栈中
                st.push(next);
                visited[next] = true; // 标记该节点已经被访问
                cout << next << " "; // 输出遍历到的节点
                has_unvisited = true;
                break;
            }
        }
        if (!has_unvisited) { // 如果当前节点没有未访问的邻接节点，则将其出栈
            st.pop();
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入图的顶点数和边数
    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) { // 输入每条边连接的两个顶点
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u); // 由于是无向图，所以需要添加两条边
    }
    vector<bool> visited(n, false);
    dfs(graph, 0, visited); // 从0号顶点开始进行深度优先搜索遍历
    cout << endl;
    visited.assign(n, false);
    dfs_iterative(graph, 0, visited); // 从0号顶点开始进行迭代式深度优先搜索遍历
    cout << endl;
    return 0;
}