17370845950

#include 
#include 
using namespace std;

void dfs(int u, vector& visited, const vector>& graph) {
    visited[u] = true;
    cout << u << " ";  // 访问操作（可替换为其他处理）

    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v, visited, graph);
        }
    }
}

int main() {
    int n = 6;  // 顶点数
    vector> graph(n);
    // 添加边：0-1, 0-2, 1-3, 1-4, 2-5
    graph[0] = {1, 2};
    graph[1] = {0, 3, 4};
    graph[2] = {0, 5};
    graph[3] = {1};
    graph[4] = {1};
    graph[5] = {2};

    vector visited(n, false);
    cout << "DFS遍历顺序: ";
    dfs(0, visited, graph);  // 从顶点0开始
    cout << endl;
    return 0;
}

#include 
#include 
#include 
using namespace std;

void dfs_iterative(int start, const vector>& graph) {
    int n = graph.size();
    vector visited(n, false);
    stack st;
    
    st.push(start);
    visited[start] = true;
    cout << start << " ";

    while (!st.empty()) {
        int u = st.top();
        st.pop();

        // 注意：这里要倒序遍历邻接点，才能和递归版顺序一致（可选）
        for (auto it = graph[u].rbegin(); it != graph[u].rend(); ++it) {
            int v = *it;
            if (!visited[v]) {
                visited[v] = true;
                cout << v << " ";
                st.push(v);
            }
        }
    }
}