在深入学习图论算法和数据结构的过程中，有向图是一个无法绕开的核心主题。而有向图中，最基础也是最关键的概念之一，就是入度（Indegree）。无论你是正在准备算法面试，还是正在开发涉及依赖管理、任务调度或网络流分析的系统，理解入度都至关重要。
在这篇文章中，我们将像探索代码底层逻辑一样，深入剖析入度的概念。我们不仅要了解它是什么，还要知道如何高效地计算它，以及它在实际的算法场景（如拓扑排序）中扮演的角色。让我们开始这段探索之旅吧。
什么是有向图的入度？
在图论中，图是由边连接的顶点的集合。当这些边是有方向的（即从 A 指向 B），我们就称之为有向图。
对于图中的任意一个顶点 V，它的入度定义为：以该顶点为终点的入边的数量。
简单来说，如果你把每一个顶点看作一个“终点”，那么箭头指向它的线条总数，就是它的入度。
#### 入度与树结构的关系
为了更好地理解其重要性，我们可以将其与熟悉的树形结构进行对比：
- 在树中：除了根节点没有父节点外，其他每个节点都只有一条入边（即只有一个父节点）。因此，在标准的树结构中，节点的入度通常为 1。
- 在图中：情况变得更加复杂。如果我们在遍历时发现某个节点的入度大于 1，这通常意味着出现了“多父节点”的情况，即该数据结构已经从简单的树演变成了通用的图，或者图中存在环。
#### 入度为 0 的特殊含义
- 根节点或源点：如果一个节点的入度为 0，这意味着没有任何箭头指向它。在拓扑结构或任务流中，它通常代表“起始点”或“根节点”。
- 孤立节点：在非连通图中，入度为 0（同时出度也可能为 0）的节点可能是一个完全孤立的顶点。
这些特性是许多高级算法（如拓扑排序、循环检测）的基础判断依据。
直观理解：如何手动计算入度？
在编写代码之前，让我们先通过一个直观的图示来手动计算入度。这将帮助我们理清算法的思路。
让我们分析上图中的顶点 V4：
- 我们要寻找所有指向 V4 的箭头。
- 可以看到，有两条边分别指向它：e3 和 e4。
- 因此，V4 的入度为 2。
以此类推，我们可以列出图中其他节点的入度分析：
- V5: 只有边 e5 指向它，所以 Indegree(V5) = 1。
- V1: 只有边 e6 指向它，所以 Indegree(V1) = 1。
- V2: 边 e1 和 e7 都指向它，所以 Indegree(V2) = 2。
- V3: 只有边 e2 指向它，所以 Indegree(V3) = 1。
虽然手动计算对于小图来说很快，但在处理成千上万个节点的真实数据时，我们需要一种自动化的、基于邻接表的高效算法。
核心算法：利用邻接表计算入度
在现代编程中，我们通常使用邻接表 来存储图，因为它比邻接矩阵更节省空间。邻接表的本质是一个数组，其中索引 INLINECODEdad205da 代表顶点 INLINECODEf52a1652，而该索引对应的列表存储了所有从 i 出发指向的邻居节点。
#### 算法设计思路
利用邻接表计算入度的核心思想是“反向计数”：
- 初始化：创建一个大小为顶点总数 INLINECODEca9fc5e5 的数组 INLINECODE91074884，并将所有元素初始化为 0。这里的 INLINECODEa3b86975 将用来存储顶点 INLINECODE96b421bb 的入度。
- 遍历所有节点：我们需要遍历邻接表中的每一个节点
i（即源节点）。 - 遍历邻居列表：对于节点 INLINECODE48d5538b，获取它的邻居列表 INLINECODE7c3cc307。列表中的每一个元素 INLINECODE84c4b81d，都代表存在一条从 INLINECODE5e58143e 指向
element的边。 - 更新计数：既然有边指向 INLINECODE4ef8c646，我们就将 INLINECODEa395d428 的值加 1。
这种方法的时间复杂度是 O(V + E)，其中 V 是顶点数，E 是边数。我们需要访问每个顶点一次，并遍历每条边一次。这是图论算法中最优的时间复杂度之一。
代码实现与深度解析
下面我们将通过 C++ 和 Java 两种主流语言来实现上述逻辑。为了让你更好地理解，我在代码中添加了详细的中文注释。
#### C++ 实现示例
C++ 的 vector 非常适合实现邻接表。我们将使用范围for循环来简化代码结构。
#include
#include
using namespace std;
// 核心函数：计算并打印每个顶点的入度
// 参数 adjList: 图的邻接表表示
// 参数 n: 图中顶点的总数
void findInDegree(const vector<vector>& adjList, int n)
{
// 1. 初始化入度数组，所有元素默认为 0
vector inDegree(n, 0);
// 2. 遍历邻接表
// list 引用了当前顶点 i 的所有出边邻居
for (const vector& list : adjList)
{
// 遍历当前顶点 i 的每一个邻居
for (int element : list)
{
// 对于每一条边 i -> element
// element 的入度需要增加 1
inDegree[element]++;
}
}
// 3. 输出结果
for (int k = 0; k < n; k++)
{
cout << "节点 " << k << " 的入度是: " << inDegree[k] << endl;
}
}
int main()
{
// 构建图的邻接表
// 这是一个包含 7 个节点（索引 0 到 6）的图结构
vector<vector> adjacency = {
{3, 4}, // 节点 0 指向 3 和 4
{3, 2}, // 节点 1 指向 3 和 2
{}, // 节点 2 没有出边
{2, 4}, // 节点 3 指向 2 和 4
{2, 3}, // 节点 4 指向 2 和 3
{1, 4, 6}, // 节点 5 指向 1, 4 和 6
{5} // 节点 6 指向 5
};
int n = adjacency.size();
cout << "正在计算图入度..." << endl;
findInDegree(adjacency, n);
return 0;
}
#### Java 实现示例
在 Java 中，我们通常使用 ArrayList 来存储动态列表。注意 Java 的集合类处理方式的细微差别。
import java.util.*;
class GraphDemo {
static void findInDegree(List<List> adjList, int n)
{
// 1. 初始化入度数组
int[] inDegree = new int[n];
// 2. 遍历邻接表中的每一个节点对应的列表
// 外层循环遍历源节点
for (List list : adjList) {
// 内层循环遍历目标节点
for (int element : list) {
// 每发现一条边，对应目标节点的入度 +1
inDegree[element]++;
}
}
// 3. 打印结果
for (int k = 0; k < n; k++) {
System.out.println("节点 " + k + " 的入度是: " + inDegree[k]);
}
}
public static void main(String args[])
{
// 初始化图的邻接表
List<List> adjacency = new ArrayList();
// 添加边的过程（构建图）
adjacency.add(new ArrayList(Arrays.asList(3, 4))); // Node 0
adjacency.add(new ArrayList(Arrays.asList(3, 2))); // Node 1
adjacency.add(new ArrayList(Arrays.asList())); // Node 2 (Isolated source)
adjacency.add(new ArrayList(Arrays.asList(2, 4))); // Node 3
adjacency.add(new ArrayList(Arrays.asList(2, 3))); // Node 4
adjacency.add(new ArrayList(Arrays.asList(1, 4, 6))); // Node 5
adjacency.add(new ArrayList(Arrays.asList(5))); // Node 6
int n = adjacency.size();
System.out.println("正在计算图入度...");
findInDegree(adjacency, n);
}
}
进阶应用：拓扑排序与 Kahn 算法
你可能会问，计算入度到底有什么实际用途？除了统计信息，它最著名的应用之一就是拓扑排序。
假设你正在开发一个构建系统（类似于 Make 或 Maven），或者正在设计大学课程修读计划。任务 A 可能依赖于任务 B。我们如何找到一个合法的执行顺序，使得所有依赖关系都得到满足？
Kahn 算法就是利用入度来解决这个问题的经典方案：
- 计算入度：首先使用我们上面介绍的方法，计算图中所有节点的入度。
- 零入度队列：将所有入度为 0 的节点加入一个队列。这些节点不需要任何前置条件，可以直接执行。
- 处理流程：
* 从队列中取出一个节点 u，将其加入排序结果。
* 遍历 INLINECODEd41a8b19 的所有邻居节点 INLINECODEc9758acc。
* 将 INLINECODE8cf21588 的入度减 1（相当于移除了来自 INLINECODEde71991a 的依赖）。
* 如果 INLINECODE338f186e 的入度变为 0，则将 INLINECODE6229ade9 加入队列。
- 检测环：如果最终排序结果的节点数小于图的总节点数，说明图中存在环（即循环依赖），拓扑排序无法完成。
可以看到，准确、快速地计算入度是执行 Kahn 算法的前提条件。
实际开发中的最佳实践与注意事项
作为开发者，我们在实现图算法时，除了写出能运行的代码，还需要考虑代码的健壮性和可维护性。
#### 1. 编号从 1 开始还是 0 开始？
在上面的示例中，我们假设节点的索引是 INLINECODE6f540ed6 到 INLINECODE1106383b。但在很多实际问题（如竞赛题目或特定 API 接口）中，节点编号可能是从 INLINECODE1b4608dd 到 INLINECODEd416a119。
- 解决方案：在这种情况下，创建数组时建议大小声明为 INLINECODE4c8db0bd，并忽略索引 INLINECODE5e39eea9 的位置。这样可以避免繁琐的
index - 1转换，减少出错几率。
// 如果节点是 1 到 N
vector inDegree(n + 1, 0);
#### 2. 自环的处理
如果一个节点有一条边指向它自己（例如 A -> A），这算入度吗？
- 结论：算的。我们的算法逻辑（
inDegree[element]++）会自动处理这种情况。自环既增加出度，也增加入度。
#### 3. 稀疏图 vs 稠密图
我们讨论的基于邻接表的算法对于稀疏图（边数远小于节点数的平方）非常高效，空间占用也是 O(V + E)。
如果你遇到的是稠密图（几乎所有点之间都有边），邻接矩阵（二维数组 adjMatrix[u][v] = 1）可能会更方便。计算入度时，只需要简单地按列求和即可。但在大多数互联网应用场景（如社交网络关注关系、网页链接）中，图都是稀疏的，因此邻接表是首选。
#### 4. 多线程并发计算
如果你的图规模非常巨大（比如整个互联网的链接图），单线程遍历可能会很慢。
- 优化思路：入度计算是一个天然可并行的操作。你可以将顶点集切割成多个分片，每个线程处理一部分顶点的出边，并更新一个支持原子操作（Atomic Integer）的
inDegree数组，或者使用分片计数最后合并结果。这可以将计算速度线性提升。
常见错误排查
在编写相关代码时，新手容易陷入以下陷阱：
- 混淆入度和出度：在遍历邻接表时，容易误以为是计算当前节点的度数。请记住：邻接表存储的是“从哪里来”，而我们需要统计的是“到哪里去”。所以是 INLINECODE1412bfef，而不是 INLINECODE6538b516。
- 数组越界：如果邻接表数据有误，包含了不存在的节点 ID，直接作为数组索引会导致程序崩溃。在处理外部输入数据时，务必进行边界检查。
- 重置计数器：在多次调用算法或处理多组测试数据时，记得清空或重置
inDegree数组，否则上次计算的结果会干扰本次计算。
总结
在这篇文章中，我们深入探讨了有向图中看似简单却极其重要的概念——入度。我们从数学定义出发，结合具体的图示进行了直观分析，并最终落地到 C++ 和 Java 的代码实现。
更重要的是，我们讨论了拓扑排序这一实际应用场景，以及在实际工程中处理大规模图数据时的注意事项。
掌握入度的计算，是你迈向高级图算法（如 A* 搜索、最大流算法）的重要基石。希望下次当你面对一个复杂的依赖图或网络结构时，你能自信地说：“我知道该怎么处理了，先计算入度！”
希望这篇文章对你有所帮助。如果你有任何疑问或想要探讨更复杂的场景，欢迎在评论区留言，我们可以继续交流。