有向图顶点的度数计算

### 有向图中顶点的入度和出度计算

在有向图中，每个顶点有两个重要的属性：入度 (in-degree) 和出度 (out-degree)。对于给定的一个有向图 G=(V,E)，其中 V 是顶点集合而 E 是边集：

- **入度**是指指向某个特定顶点 v 的边的数量；
- **出度**是从某一个特定顶点出发到达其他顶点的边数量。

为了有效地计算这些值，在构建好有向图的数据结构之后（通常是通过邻接表或邻接矩阵），可以遍历整个图形来统计各个节点的相关信息[^2]。

当采用邻接表作为存储方式时，可以通过如下算法实现对所有顶点出入度的同时记录:

void calculateDegree(vector<vector<int>>& graph, vector<int>& inDegree, vector<int>& outDegree){
    int n = graph.size();
    inDegree.resize(n);
    outDegree.resize(n);

    for(int i=0; i<n; ++i){ // 遍历每一个结点及其相连的边
        for(auto& neighbor : graph[i]){
            ++inDegree[neighbor]; // 对于每条从当前结点发出到另一个结点 u 的边，增加u的入度计数器
        }
        outDegree[i]=graph[i].size(); // 当前结点所连接出去的边数目即为其自身的出度
    }
}

上述函数接收三个参数：`graph` 表示以邻接列表形式表示的有向图；两个整型数组 `inDegree[]` 和 `outDegree[]` 分别用于保存对应位置上顶点的入度与出度结果。此过程会更新这两个数组中的数据以便后续查询使用[^1]。

如果选择了邻接矩阵的方式来表达这个关系，则可以直接利用其特性快速获取任意两点间是否存在路径的信息，并据此调整相应顶点的度量指标。例如，假设我们有一个布尔类型的二维数组 adjMatrix 来描述这种关联性，那么就可以按照下面的方式来进行操作[^3]:

for(int row = 0;row < numVertices;++row){
    for(int col = 0;col < numVertices;++col){
        if(adjMatrix[row][col]==true){
           ++outDegree[row];
           ++inDegree[col];
        }
     }
}

这段代码同样实现了相同的功能——它迭代访问了所有的可能组合并依据实际存在的链接情况修改对应的入/出度变量。