使用c++实现图的邻接表表示，并创建图；对邻接表表示的图实现深度优先遍历

在 C++ 中，我们可以使用邻接表（Adjacency List）来表示图，因为邻接表非常适合表示稀疏图，即边的数量远小于顶点数的平方的情况。邻接表通常是一个数组，每个元素对应一个顶点，它存储了一个链表，链表中的节点代表该顶点的所有邻居。

首先，我们创建一个简单的邻接表结构：

#include <iostream>
#include <list>

// 定义一个结构体表示顶点
struct Vertex {
    int id;
    std::list<int> neighbors; // 链表存放邻居顶点的id
};

// 图类
class Graph {
private:
    std::vector<Vertex> vertices; // 存放所有顶点

public:
    void addVertex(int id) {
        vertices.push_back({id, std::list<int>()});
    }

    void addEdge(int src, int dest) {
        vertices[src].neighbors.push_back(dest);
        vertices[dest].neighbors.push_back(src); // 如果图是非互连的，需要添加双向链接
    }

    // 深度优先搜索函数，这里仅提供基本框架
    void dfs(int start) {
        std::list<int>& vertexList = vertices[start].neighbors;
        bool* visited = new bool[vertexList.size()] {false}; // 初始化访问标记

        for (int i = 0; i < vertexList.size(); ++i) {
            if (!visited[i]) {
                visited[i] = true; // 标记已访问
                dfs(vertexList[i]); // 递归遍历邻居
            }
        }

        delete[] visited;
    }
};

接下来，你可以创建一个图并添加一些顶点和边，然后调用 `dfs` 函数开始深度优先遍历：

Graph graph;
graph.addVertex(0); // 添加第一个顶点
graph.addVertex(1);
graph.addVertex(2);

graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2); // 示例图

graph.dfs(0); // 从顶点0开始深度优先遍历