邻接表求图的入度出度

邻接表是一种图的存储结构，可以用来表示有向图和无向图。在邻接表中，每个顶点都对应一个链表，链表中存储了该顶点所指向的其他顶点。邻接表可以用来求图的入度和出度。

求图的入度：对于有向图中的每个顶点，遍历整个邻接表，统计指向该顶点的边的数量即为该顶点的入度。

求图的出度：对于有向图中的每个顶点，遍历该顶点对应的链表，统计链表中边的数量即为该顶点的出度。

下面是C++代码实现：

#include <iostream>
using namespace std;

#define MaxSize 20

struct Node {
    int weight;
    int index;
    struct Node *next;
};

struct HNode {
    char nodeData;
    struct Node *next;
};

struct Graph {
    int vertexNum;
    int arcNum;
    bool isDireted;
    HNode verList[MaxSize];
};

// 计算顶点v的入度
int getInDegree(Graph G, int v) {
    int inDegree = 0;
    for (int i = 0; i < G.vertexNum; i++) {
        Node *p = G.verList[i].next;
        while (p != NULL) {
            if (p->index == v) {
                inDegree++;
            }
            p = p->next;
        }
    }
    return inDegree;
}

// 计算顶点v的出度
int getOutDegree(Graph G, int v) {
    int outDegree = 0;
    Node *p = G.verList[v].next;
    while (p != NULL) {
        outDegree++;
        p = p->next;
    }
    return outDegree;
}

// 计算出度最大的顶点编号
int getMaxOutDegreeVertex(Graph G) {
    int maxOutDegree = 0;
    int maxOutDegreeVertex = -1;
    for (int i = 0; i < G.vertexNum; i++) {
        int outDegree = getOutDegree(G, i);
        if (outDegree > maxOutDegree) {
            maxOutDegree = outDegree;
            maxOutDegreeVertex = i;
        }
    }
    return maxOutDegreeVertex;
}

// 计算出度为0的顶点数
int getZeroOutDegreeVertexNum(Graph G) {
    int zeroOutDegreeVertexNum = 0;
    for (int i = 0; i < G.vertexNum; i++) {
        int outDegree = getOutDegree(G, i);
        if (outDegree == 0) {
            zeroOutDegreeVertexNum++;
        }
    }
    return zeroOutDegreeVertexNum;
}

int main() {
    // 创建一个有向图
    Graph G;
    G.vertexNum = 5;
    G.arcNum = 7;
    G.isDireted = true;
    for (int i = 0; i < G.vertexNum; i++) {
        G.verList[i].nodeData = 'A' + i;
        G.verList[i].next = NULL;
    }
    int arcs[7][2] = {{0, 1}, {0, 3}, {1, 2}, {1, 3}, {2, 4}, {3, 2}, {4, 3}};
    for (int i = 0; i < G.arcNum; i++) {
        int from = arcs[i][0];
        int to = arcs[i][1];
        Node *p = new Node;
        p->index = to;
        p->next = G.verList[from].next;
        G.verList[from].next = p;
    }

    // 计算每个顶点的入度和出度
    for (int i = 0; i < G.vertexNum; i++) {
        cout << "顶点" << G.verList[i].nodeData << "的入度为：" << getInDegree(G, i) << endl;
        cout << "顶点" << G.verList[i].nodeData << "的出度为：" << getOutDegree(G, i) << endl;
    }

    // 计算出度最大的顶点编号
    int maxOutDegreeVertex = getMaxOutDegreeVertex(G);
    cout << "出度最大的顶点编号为：" << maxOutDegreeVertex << endl;

    // 计算出度为0的顶点数
    int zeroOutDegreeVertexNum = getZeroOutDegreeVertexNum(G);
    cout << "出度为0的顶点数为：" << zeroOutDegreeVertexNum << endl;

    return 0;
}