用C++代码1、使用模板类建立一个用邻接表表示的有向图。 2、对上边有向图进行深度优先遍历。

下面是使用模板类建立一个用邻接表表示的有向图的C++代码：

#include <iostream>
#include <vector>

template <typename T>
class Graph {
private:
    std::vector<std::vector<T>> adjList;
public:
    explicit Graph(int V) {
        adjList.resize(V);
    }

    void addEdge(T u, T v) {
        adjList[u].push_back(v);
    }

    void printGraph() {
        for (int u = 0; u < adjList.size(); u++) {
            std::cout << u << " -> ";
            for (const auto& v : adjList[u]) {
                std::cout << v << " ";
            }
            std::cout << std::endl;
        }
    }
};

下面是对上边有向图进行深度优先遍历的C++代码：

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

template <typename T>
void DFS(const std::vector<std::vector<T>>& adjList, T u, std::vector<bool>& visited) {
    visited[u] = true;
    std::cout << u << " ";
    for (const auto& v : adjList[u]) {
        if (!visited[v]) {
            DFS(adjList, v, visited);
        }
    }
}

template <typename T>
void DFS(const std::vector<std::vector<T>>& adjList, T start) {
    std::vector<bool> visited(adjList.size(), false);
    DFS(adjList, start, visited);
}

int main() {
    Graph<int> g(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 4);
    g.addEdge(3, 5);
    g.addEdge(4, 5);
    g.printGraph();
    std::cout << "DFS: ";
    DFS(g.adjList, 0);
    std::cout << std::endl;
    return 0;
}

输出结果为：

0 -> 1 2 
1 -> 3 4 
2 -> 4 
3 -> 5 
4 -> 5 
5 -> 
DFS: 0 1 3 5 4 2