（6） 在邻接表存储结构下求图G中每个顶点的入度

对于邻接表存储的图G，可以通过遍历每个顶点的邻接表，来统计每个顶点的入度。具体步骤如下：

1. 初始化每个顶点的入度为0。

2. 遍历每个顶点的邻接表，对于邻接表中的每个节点，将对应的顶点的入度加1。

3. 统计得到每个顶点的入度。

以下是C++代码实现：

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

// 邻接表存储的图结构
class Graph {
public:
    int V; // 顶点数
    vector<vector<int>> adj; // 邻接表

    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    // 添加一条边
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
};

// 求每个顶点的入度
vector<int> getIndegree(Graph& G) {
    vector<int> indegree(G.V, 0); // 初始化每个顶点的入度为0

    // 遍历每个顶点的邻接表，对于邻接表中的每个节点，将对应的顶点的入度加1
    for (int u = 0; u < G.V; u++) {
        for (auto v : G.adj[u]) {
            indegree[v]++;
        }
    }

    return indegree;
}

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

    vector<int> indegree = getIndegree(G);

    // 输出每个顶点的入度
    for (int u = 0; u < G.V; u++) {
        cout << "Vertex " << u << " indegree: " << indegree[u] << endl;
    }

    return 0;
}

输出结果为：

Vertex 0 indegree: 0
Vertex 1 indegree: 1
Vertex 2 indegree: 2
Vertex 3 indegree: 1
Vertex 4 indegree: 1