写一个C++版本的深度优先搜索算法

在C++中，我们可以使用递归的方式来实现深度优先搜索（Depth First Search，DFS）。这是一种用于遍历或搜索树或图数据结构的有效算法。下面是一个基本的C++ DFS实现例子：

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

// 用邻接列表表示图
using namespace std;

class Graph {
private:
    vector<vector<int>> adj; // 邻接表

public:
    Graph(int vertices) {
        adj.resize(vertices);
    }

    void addEdge(int src, int dest) {
        adj[src].push_back(dest);
        adj[dest].push_back(src); // 图是非定向的，所以添加双向边
    }

    // 从起点进行深度优先搜索
    void dfs(int start) {
        bool visited[] = {false}; // 初始化所有节点未访问
        stack<int> s;

        s.push(start);
        visited[start] = true;

        while (!s.empty()) {
            int node = s.top();
            cout << node << " "; // 输出当前节点
            s.pop();

            for (int neighbor : adj[node]) {
                if (!visited[neighbor]) {
                    s.push(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
};

int main() {
    Graph g(4); // 创建一个有4个顶点的图
    g.addEdge(0, 1); // 添加边
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);

    cout << "Depth First Traversal (starting from vertex 2): ";
    g.dfs(2); // 从顶点2开始搜索
    return 0;
}

在这个例子中，我们首先创建了一个图并定义了邻接表。`dfs`函数接收起始节点，然后使用栈来存储待访问的节点。每当我们找到一个新节点，就标记它为已访问，并将它的相邻节点推入栈中，直到栈为空为止。