使用C++实现图的深度优先遍历算法

在C++中，我们可以使用递归或栈来实现深度优先遍历。以下是使用栈实现深度优先遍历的基本步骤：

1. 创建一个visited数组来记录每个节点是否被访问过，初始值为false。
2. 创建一个栈，将起始节点入栈。
3. 当栈不为空时，弹出栈顶元素并访问它，将其标记为已访问。
4. 遍历该节点的所有未访问的相邻节点，将它们入栈。
5. 重复步骤3和步骤4，直到栈为空。

下面是一个使用栈实现深度优先遍历的C++代码示例：

void DFS(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    stack<int> s;
    s.push(start);
    while (!s.empty()) {
        int node = s.top();
        s.pop();
        if (!visited[node]) {
            visited[node] = true;
            // 访问节点node
            for (int i = 0; i < graph[node].size(); i++) {
                int neighbor = graph[node][i];
                if (!visited[neighbor]) {
                    s.push(neighbor);
                }
            }
        }
    }
}

其中，start表示起始节点，graph是邻接表表示的图，visited是记录节点是否被访问过的数组。