在有向图中，顶点的度需要区分为入度和出度两种形式。**入度是指指向该顶点的边的数量，出度是指从该顶点出发的边的数量，总度通常为入度与出度之和**。在 Java 中，可以通过邻接表、邻接矩阵或边集合等结构遍历统计这些数量。理解有向图顶点度的计算方式，是掌握图论算法、拓扑排序、最短路径和网络分析等应用的基础。

## 一、有向图顶点度的基本概念

在图论中，图分为无向图与有向图两大类。无向图中的边没有方向，因此每条边都会同时增加两个顶点的度；而在有向图中，边具有明确方向，这使得顶点的“度”被拆分为入度（In-degree）和出度（Out-degree）。**入度表示有多少条边指向该顶点，出度表示有多少条边从该顶点出发**，这是计算有向图顶点度的核心逻辑。

例如，在一个包含顶点 A、B、C 的有向图中，如果存在 A→B、C→B 两条边，那么 B 的入度为 2，而出度为 0；如果存在 B→A，那么 B 的出度为 1。此时，B 的总度可视为 3，但在算法实践中，更多使用入度和出度分别统计，而不是单纯使用总度。

根据《Introduction to Algorithms》（Cormen 等，MIT Press，2009）中的图论定义，有向图 G=(V,E) 中，某顶点 v 的入度记为 deg⁻(v)，出度记为 deg⁺(v)。这一表示方法在学术界与工程实践中均被广泛采用，是 Java 实现时的理论基础。

## 二、有向图的常见存储结构对比

在 Java 中实现有向图，通常有三种主流方式：邻接矩阵、邻接表和边列表。不同结构对顶点度的计算效率有明显差异。

| 存储方式 | 空间复杂度 | 计算出度复杂度 | 计算入度复杂度 | 适用场景 |
|----------|------------|----------------|----------------|-----------|
| 邻接矩阵 | O(V²)      | O(V)           | O(V)           | 稠密图 |
| 邻接表   | O(V+E)     | O(1)~O(k)      | O(E)或预处理O(V+E) | 稀疏图 |
| 边列表   | O(E)       | O(E)           | O(E)           | 简单结构 |

从表中可以看出，**邻接表在大多数实际项目中更为高效**，尤其是在边数量远小于 V² 的情况下。Oracle 官方 Java 文档（Oracle Java Documentation，2023）中关于集合框架的说明也指出，使用 ArrayList 与 HashMap 组合构建邻接表，可以在时间与空间之间取得较好平衡。

## 三、基于邻接表计算出度的 Java 实现

在邻接表结构中，每个顶点对应一个列表，列表中存储从该顶点出发的所有邻接点。因此，**计算出度实际上等于该顶点邻接列表的长度**。

示例代码如下：

```java
import java.util.*;

public class DirectedGraph {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    public void addEdge(int from, int to) {
        adjList.putIfAbsent(from, new ArrayList<>());
        adjList.get(from).add(to);
        adjList.putIfAbsent(to, new ArrayList<>());
    }

    public int getOutDegree(int vertex) {
        return adjList.getOrDefault(vertex, new ArrayList<>()).size();
    }
}
```

在这个实现中，顶点的出度计算复杂度为 O(1)（平均情况下）。由于邻接表天然存储“从谁出发”的信息，因此出度统计极其直接，适用于拓扑排序和路径搜索等算法。

## 四、基于邻接表计算入度的 Java 实现

与出度不同，邻接表默认并不存储“指向谁”的信息，因此**计算入度通常需要遍历所有顶点的邻接列表**。这种方式时间复杂度为 O(V+E)。

实现示例如下：

```java
public int getInDegree(int vertex) {
    int inDegree = 0;
    for (Map.Entry<Integer, List<Integer>> entry : adjList.entrySet()) {
        for (int neighbor : entry.getValue()) {
            if (neighbor == vertex) {
                inDegree++;
            }
        }
    }
    return inDegree;
}
```

在图规模较大时，频繁遍历会影响性能。因此在工程实践中，通常在添加边时同步维护一个入度数组，例如：

```java
private Map<Integer, Integer> inDegreeMap = new HashMap<>();

public void addEdge(int from, int to) {
    adjList.putIfAbsent(from, new ArrayList<>());
    adjList.get(from).add(to);
    adjList.putIfAbsent(to, new ArrayList<>());
    inDegreeMap.put(to, inDegreeMap.getOrDefault(to, 0) + 1);
}
```

这种方式可以将入度查询复杂度降低至 O(1)，非常适合需要频繁查询入度的场景，如拓扑排序。

## 五、基于邻接矩阵计算顶点度

邻接矩阵使用二维数组 matrix[i][j] 表示是否存在从 i 到 j 的边。此时：

- 出度 = 第 i 行中 1 的个数  
- 入度 = 第 i 列中 1 的个数  

示例代码如下：

```java
public int getOutDegree(int[][] matrix, int vertex) {
    int count = 0;
    for (int j = 0; j < matrix.length; j++) {
        if (matrix[vertex][j] == 1) {
            count++;
        }
    }
    return count;
}

public int getInDegree(int[][] matrix, int vertex) {
    int count = 0;
    for (int i = 0; i < matrix.length; i++) {
        if (matrix[i][vertex] == 1) {
            count++;
        }
    }
    return count;
}
```

这种方法逻辑简单，但空间消耗大。当顶点数量达到数万级时，O(V²) 的空间开销可能无法接受，因此在实际 Java 项目中，多用于教学或小规模图结构。

## 六、有向图顶点度在算法中的应用

理解有向图顶点的度不仅仅是统计问题，更是多种图算法的核心。例如，拓扑排序算法中，**每次选择入度为 0 的顶点进行删除操作**，并更新其邻接顶点的入度。这种机制依赖对入度的准确维护。

在网络流算法中，出度较大的节点往往代表数据分发中心；在社交网络分析中，入度高的节点可能代表高关注度对象。因此，顶点度不仅是数据结构问题，更是分析结构关系的重要指标。

根据 MIT OpenCourseWare 图算法课程（2022）讲解，入度与出度统计是实现有向无环图处理与依赖关系分析的基础操作。在 Java 实践中，良好的数据结构设计直接决定算法效率。

## 七、大规模图结构下的性能优化建议

在实际工程中，尤其是数据规模较大的场景，单纯遍历统计入度可能会带来性能瓶颈。此时应优先采用**邻接表 + 入度数组同步维护**的方式，避免重复遍历。

若图结构频繁变动，可以考虑封装一个 Graph 类，在添加和删除边时同时更新入度与出度信息，从而保证查询为 O(1)。此外，对于多线程环境下的图结构操作，需要使用线程安全的集合或加锁机制，避免入度统计错误。

如果图结构用于项目依赖管理、任务调度或流程引擎中，建议在系统设计初期就明确入度与出度的维护策略。部分研发团队在管理复杂依赖关系时，会结合专业研发管理工具，如 [PingCode](https://PingCode.com?utm_source=insights&utm_medium=%E5%93%81%E7%89%8C%E8%AF%8D) 进行依赖建模与任务流转，但核心逻辑仍基于有向图与顶点度计算原理。

## 八、常见错误与面试高频问题解析

在 Java 面试中，“有向图顶点的度怎么算”是常见问题，常见错误包括混淆无向图与有向图的度定义，以及忽略入度与出度的区别。还有一些开发者在使用邻接表时误以为列表长度即为总度，而忽略入度计算。

需要特别注意的是，在有向图中，所有顶点入度之和等于所有顶点出度之和，且都等于边数 E。这是图论中的基本性质，可用于调试验证。

例如，如果一个图有 10 条边，那么所有顶点的出度之和必然为 10，入度之和也为 10。这个性质在排查统计逻辑错误时非常有效。

## 九、总结与未来趋势

综上所述，**有向图顶点的度包括入度与出度两部分，Java 实现方式取决于所采用的存储结构**。邻接表适用于大多数场景，配合入度同步维护可以实现高效查询；邻接矩阵适合小规模或教学环境。理解度的计算不仅有助于算法实现，更是构建复杂依赖系统的基础。

随着数据规模的持续增长和图计算技术的发展，图数据库和分布式图计算框架逐渐兴起，但底层逻辑依然建立在顶点度计算之上。未来在实时计算、依赖分析和智能调度领域，有向图与顶点度统计仍将发挥重要作用。掌握其原理与 Java 实现方式，是每位开发者必须具备的核心能力。

参考与资料来源  
Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms, MIT Press, 2009.  
Oracle. Java Platform, Standard Edition Documentation, 2023.

顶点的入度是指指向该顶点的边的数量。可以遍历图中所有的边，统计终点为该顶点的边数量。在Java中，可以通过邻接表或邻接矩阵遍历来实现，记录所有指向目标顶点的边即可得到入度。

计算顶点入度的方法

在有向图中，如何用Java代码计算某个顶点的入度？

有向图中如何计算顶点的入度？

出度是指从该顶点出发的边的数量。Java实现时，可以根据邻接表结构直接获取该顶点的邻接点集合大小，或在邻接矩阵中统计对应行中非零元素的数量，得到出度值。

计算顶点出度的方法

在有向图中，使用Java如何计算某个顶点的出度？

有向图顶点的出度怎么算？

可以遍历图中的所有边，对每条边的起点顶点出度加一，终点顶点入度加一。使用二维数组或邻接表存储图时，维护两个数组分别记录每个顶点的入度和出度，遍历一遍边集合即可同时更新两者。

同时计算入度与出度的方法

有没有什么高效的算法或代码结构可以同时获取每个顶点的入度和出度？

Java中如何同时计算有向图顶点的入度和出度？

PingCodeDocs

有向图顶点的度分为入度和出度，入度是指指向该顶点的边数量，出度是从该顶点出发的边数量，总度为两者之和。在 Java 中可通过邻接表、邻接矩阵或边列表进行统计，其中邻接表结合入度同步维护效率较高，适用于大规模图结构和算法应用，如拓扑排序与依赖分析。掌握入度与出度的计算方式，是实现图算法和构建复杂系统结构的基础能力。

有向图顶点的度怎么算java