对图的深度优先遍历非递归c++

深度优先遍历（DFS）是一种遍历图的方法，可以使用递归或非递归的方式实现。下面是一个非递归的深度优先遍历的c++实现：

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

void dfs(vector<vector<int>>& graph, int start) {
    stack<int> s;
    vector<bool> visited(graph.size(), false);
    s.push(start);
    visited[start] = true;
    while (!s.empty()) {
        int node = s.top();
        s.pop();
        cout << node << " ";
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                s.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

int main() {
    // 构造一个图
    vector<vector<int>> graph = {{1, 2}, {0, 2, 3}, {0, 1, 3}, {1, 2}};
    dfs(graph, 0); // 从节点0开始深度优先遍历
    return 0;
}

该代码使用了一个栈和一个布尔数组来实现非递归的深度优先遍历。首先将起始节点放入栈中，并将其标记为已访问。然后，当栈不为空时，从栈中取出一个节点并输出它，然后将其未访问的邻居节点放入栈中，并将其标记为已访问。重复此过程，直到栈为空。