用c++编写图的深度优先遍历程序

以下是使用C++编写图的深度优先遍历程序的示例代码：

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

// 定义图的邻接表存储结构
class Graph {
public:
    int V; // 图的顶点数
    vector<int> *adj; // 存储每个顶点的邻接点

    Graph(int V) {
        this->V = V;
        adj = new vector<int>[V];
    }

    // 添加一条边
    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }

    // 深度优先遍历
    void DFS(int s) {
        // 标记所有顶点为未访问
        bool *visited = new bool[V];
        for (int i = 0; i < V; i++) {
            visited[i] = false;
        }

        // 创建一个栈来存储遍历顺序
        stack<int> stack;

        // 将起始顶点标记为已访问，并将其压入栈中
        visited[s] = true;
        stack.push(s);

        while (!stack.empty()) {
            // 弹出栈顶元素并输出
            s = stack.top();
            cout << s << " ";
            stack.pop();

            // 遍历所有邻接点，将未访问的邻接点标记为已访问并压入栈中
            for (auto i = adj[s].begin(); i != adj[s].end(); ++i) {
                if (!visited[*i]) {
                    visited[*i] = true;
                    stack.push(*i);
                }
            }
        }
    }
};

int main() {
    // 创建一个包含4个顶点的图
    Graph g(4);

    // 添加边
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    // 从顶点0开始进行深度优先遍历
    cout << "Depth First Traversal (starting from vertex 0): ";
    g.DFS(0);

    return 0;
}