图的遍历算法在C++中如何实现

在C++中实现图的遍历算法通常使用深度优先搜索（DFS）和广度优先搜索（BFS）两种方法。

以下是一个使用邻接表表示图并实现DFS和BFS算法的示例代码：

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

using namespace std;

class Graph {
private:
    int V;
    vector<vector<int>> adj;

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

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    void DFSUtil(int v, vector<bool>& visited) {
        visited[v] = true;
        cout << v << " ";

        for (int u : adj[v]) {
            if (!visited[u]) {
                DFSUtil(u, visited);
            }
        }
    }

    void DFS(int start) {
        vector<bool> visited(V, false);
        DFSUtil(start, visited);
    }

    void BFS(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        q.push(start);
        visited[start] = true;

        while (!q.empty()) {
            int v = q.front();
            q.pop();
            cout << v << " ";

            for (int u : adj[v]) {
                if (!visited[u]) {
                    visited[u] = true;
                    q.push(u);
                }
            }
        }
    }
};

int main() {
    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);

    cout << "DFS traversal starting from vertex 2: ";
    g.DFS(2);
    cout << endl;

    cout << "BFS traversal starting from vertex 2: ";
    g.BFS(2);
    cout << endl;

    return 0;
}

在这个示例代码中，我们首先定义了一个Graph类来表示图，并实现了addEdge、DFS和BFS方法来添加边、进行深度优先搜索和广度优先搜索。在主函数中，我们创建了一个包含4个顶点的图，添加了边，然后分别从顶点2开始进行DFS和BFS遍历。