用c++实现图的深度遍历和广度遍历

图的深度遍历和广度遍历是图论中比较基础的算法，下面是C++实现的代码：

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

using namespace std;

// 定义一个无向图类
class Graph {
private:
    int V; // 图中顶点的数量
    vector<int> *adj; // 邻接表
public:
    Graph(int V); // 构造函数
    void addEdge(int v, int w); // 添加边
    void DFS(int v); // 深度优先遍历
    void BFS(int v); // 广度优先遍历
};

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

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
    adj[w].push_back(v);
}

void Graph::DFS(int v) {
    // 创建一个 bool 类型的数组，表示每个顶点是否被访问
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    // 创建一个栈，用于存储已经经过的顶点
    stack<int> s;

    // 将起始顶点加入栈中
    s.push(v);

    while (!s.empty()) {
        // 取出栈顶元素
        v = s.top();
        s.pop();

        // 如果该顶点还没有被访问过，就将其标记为已访问
        if (!visited[v]) {
            cout << v << " ";
            visited[v] = true;
        }

        // 遍历该顶点的所有邻接顶点
        for (auto it = adj[v].begin(); it != adj[v].end(); ++it) {
            if (!visited[*it]) {
                // 如果邻接顶点还没有被访问过，就将其加入栈中
                s.push(*it);
            }
        }
    }

    delete[] visited;
}

void Graph::BFS(int v) {
    // 创建一个 bool 类型的数组，表示每个顶点是否被访问
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    // 创建一个队列，用于存储已经经过的顶点
    queue<int> q;

    // 将起始顶点加入队列中
    q.push(v);

    while (!q.empty()) {
        // 取出队首元素
        v = q.front();
        q.pop();

        // 如果该顶点还没有被访问过，就将其标记为已访问
        if (!visited[v]) {
            cout << v << " ";
            visited[v] = true;
        }

        // 遍历该顶点的所有邻接顶点
        for (auto it = adj[v].begin(); it != adj[v].end(); ++it) {
            if (!visited[*it]) {
                // 如果邻接顶点还没有被访问过，就将其加入队列中
                q.push(*it);
            }
        }
    }

    delete[] visited;
}

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    cout << "DFS: ";
    g.DFS(0);
    cout << endl;

    cout << "BFS: ";
    g.BFS(0);
    cout << endl;

    return 0;
}

上面的代码中，我们定义了一个 `Graph` 类来表示一个无向图，其中包含了两个成员函数 `DFS()` 和 `BFS()` 分别用于实现深度优先遍历和广度优先遍历。在 `DFS()` 和 `BFS()` 函数中，我们都创建了一个 bool 类型的数组 `visited`，用于表示每个顶点是否被访问过。然后分别使用栈和队列来存储已经经过的顶点，从而实现遍历整个图的过程。

最后我们在 `main()` 函数中创建了一个 `Graph` 对象 `g`，并添加了一些边。然后分别调用 `DFS()` 和 `BFS()` 函数来遍历整个图。