用邻接表创建图且深度优先遍历c➕➕

好的，我来回答你的问题。

首先，邻接表是一种用于表示图的数据结构，它由一组链表组成，每个链表都存储从某个顶点出发所能到达的所有顶点。邻接表比邻接矩阵更加节省空间，因为它只存储了实际存在边的信息。

接下来是深度优先遍历。深度优先遍历是一种图遍历算法，它从图中某个顶点出发，访问这个顶点，然后访问它的每个邻接顶点，再依次对邻接顶点进行深度优先遍历。在遍历时，需要标记每个顶点是否已经被访问过，以避免重复访问。

下面是使用邻接表实现深度优先遍历的C++代码：

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

// 定义邻接表中的链表节点
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 定义图
class Graph {
public:
    int V; // 顶点数
    vector<ListNode*> adjList; // 邻接表

    Graph(int V) {
        this->V = V;
        adjList.resize(V);
        for (int i = 0; i < V; i++) {
            adjList[i] = NULL;
        }
    }

    // 添加边
    void addEdge(int u, int v) {
        ListNode *node = new ListNode(v);
        node->next = adjList[u];
        adjList[u] = node;
    }

    // 深度优先遍历
    void DFS(int s) {
        // 标记顶点是否已经被访问过
        vector<bool> visited(V, false);

        stack<int> stk;
        stk.push(s);

        while (!stk.empty()) {
            int u = stk.top();
            stk.pop();

            if (!visited[u]) {
                cout << u << " ";
                visited[u] = true;
            }

            // 将邻接顶点加入栈中
            ListNode *cur = adjList[u];
            while (cur != NULL) {
                int v = cur->val;
                if (!visited[v]) {
                    stk.push(v);
                }
                cur = cur->next;
            }
        }
    }
};

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 << "深度优先遍历结果：" << endl;
    g.DFS(2);

    return 0;
}

在上面的代码中，我们首先定义了一个邻接表中的链表节点 `ListNode`，然后定义了一个图类 `Graph`，其中包含了顶点数和邻接表。在 `Graph` 类中，我们实现了一个函数 `addEdge`，用于添加边。接着，我们实现了深度优先遍历算法 `DFS`，其中使用了一个 `stack` 来辅助遍历。最后，在 `main` 函数中，我们创建了一个图，并对其进行深度优先遍历。

希望这个回答能够帮到你！