**有向图的邻接表在 Java 中通常通过“数组/集合 + 链表（或列表）”结构实现，本质是为每个顶点维护一个存储其出边的列表结构。相比邻接矩阵，邻接表在处理稀疏图时具有更低的空间复杂度（O(V+E)），并且更适合图遍历与算法实现。**在 Java 中，可以基于 `ArrayList<List<Integer>>`、`Map<Integer, List<Integer>>` 或自定义节点类完成构建。本文将系统讲解有向图邻接表的原理、实现方式、时间复杂度分析、应用场景及工程实践建议，帮助开发者全面掌握该数据结构。

## 一、有向图与邻接表的基本概念

在数据结构与算法领域，有向图（Directed Graph）是一种边具有方向性的图结构，通常表示为 G=(V,E)，其中 V 表示顶点集合，E 表示有序边集合。每条边 (u,v) 表示从顶点 u 指向顶点 v。**有向图的核心特征在于边的方向不可逆，这对遍历和路径计算产生重要影响。**

邻接表（Adjacency List）是一种常见的图存储方式，其基本思想是：为每个顶点维护一个列表，用于记录所有与该顶点相连的其他顶点。在有向图中，邻接表通常只存储“出边”，即从当前节点出发能够到达的节点。

根据《Introduction to Algorithms》（Cormen 等，2009）中的描述，邻接表在稀疏图场景下具有明显优势，因为其空间复杂度为 O(V+E)，而邻接矩阵为 O(V²)。当边远少于 V² 时，邻接表更节省内存。

在 Java 开发中，有向图邻接表是实现 DFS、BFS、拓扑排序、最短路径算法等图算法的基础数据结构。

## 二、Java 中邻接表的常见实现方式

在 Java 中，实现有向图邻接表主要有三种方式：基于数组的列表结构、基于 Map 的动态结构、自定义节点对象结构。不同实现方式适用于不同业务需求。

第一种方式是使用 `ArrayList<List<Integer>>`。这种方式适用于顶点编号连续的场景，例如 0 到 n-1。代码结构简单，访问效率高，是算法题中最常见的实现方式。

```java
import java.util.*;

public class DirectedGraph {
    private List<List<Integer>> adj;

    public DirectedGraph(int vertices) {
        adj = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adj.get(u).add(v);
    }

    public List<Integer> getNeighbors(int u) {
        return adj.get(u);
    }
}
```

第二种方式是使用 `Map<Integer, List<Integer>>`。这种方式适用于顶点不连续或顶点动态变化的场景。例如在社交网络图中，用户 ID 可能不是连续编号。

```java
Map<Integer, List<Integer>> graph = new HashMap<>();

public void addEdge(int u, int v) {
    graph.putIfAbsent(u, new ArrayList<>());
    graph.get(u).add(v);
}
```

第三种方式是自定义节点类，适用于复杂业务场景，例如边带权重或附加属性。

```java
class Edge {
    int target;
    int weight;

    Edge(int target, int weight) {
        this.target = target;
        this.weight = weight;
    }
}
```

**在实际工程中，推荐根据数据规模与顶点特性选择合适结构，而非固定使用某一种模板。**

## 三、邻接表与邻接矩阵对比分析

理解有向图邻接表的优势，必须将其与邻接矩阵进行对比。以下表格总结了两种结构的核心差异：

| 对比维度 | 邻接表 | 邻接矩阵 |
|----------|--------|----------|
| 空间复杂度 | O(V+E) | O(V²) |
| 查询是否存在边 | O(degree) | O(1) |
| 遍历所有邻居 | O(degree) | O(V) |
| 适用场景 | 稀疏图 | 稠密图 |
| 插入边 | O(1) | O(1) |
| 删除边 | O(degree) | O(1) |

从空间复杂度角度看，当图为稀疏图（E ≪ V²）时，邻接表节省大量内存。在大规模系统中，这种差异尤为明显。

根据《Algorithms, 4th Edition》（Sedgewick & Wayne, 2011）中的数据结构分析，现代图计算场景（如推荐系统、社交关系网络）多为稀疏图，因此邻接表成为主流实现方式。

**因此，在 Java 中实现有向图时，邻接表通常是默认优选方案。**

## 四、有向图邻接表的时间复杂度分析

时间复杂度是评价有向图邻接表实现质量的重要指标。

在邻接表结构中：

- 添加一条边的时间复杂度为 O(1)
- 查询某个顶点的所有邻居为 O(degree)
- 图的遍历时间复杂度为 O(V+E)

例如在进行深度优先搜索（DFS）时，每个顶点访问一次，每条边遍历一次，因此总复杂度为 O(V+E)。

```java
public void dfs(int node, boolean[] visited) {
    visited[node] = true;
    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited);
        }
    }
}
```

**邻接表的优势在于不会无谓扫描不存在的边。**相比邻接矩阵每次都需遍历整行，邻接表仅遍历实际存在的边，提高效率。

在大规模图计算中，例如百万级节点和千万级边，邻接表结构的性能优势会更加明显。

## 五、有向图邻接表在算法中的应用

有向图邻接表是众多图算法的基础，包括：

- 深度优先搜索（DFS）
- 广度优先搜索（BFS）
- 拓扑排序
- 强连通分量算法
- 最短路径算法（Dijkstra）

以拓扑排序为例，有向图邻接表非常适合实现 Kahn 算法或基于 DFS 的拓扑排序。

```java
public void topologicalSort() {
    boolean[] visited = new boolean[adj.size()];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < adj.size(); i++) {
        if (!visited[i]) {
            topoUtil(i, visited, stack);
        }
    }
    while (!stack.isEmpty()) {
        System.out.print(stack.pop() + " ");
    }
}
```

**在任务依赖管理、编译依赖分析、工作流调度等系统中，有向图邻接表结构是核心数据模型。**

在实际项目管理或研发流程中，复杂依赖关系也可抽象为有向图结构。例如在研发项目管理系统 [PingCode](https://PingCode.com?utm_source=insights&utm_medium=%E5%93%81%E7%89%8C%E8%AF%8D) 中，任务依赖关系本质上可以建模为有向图，通过邻接结构进行依赖分析与进度计算。这种图模型设计理念与算法中的邻接表结构高度一致。

## 六、工程实践中的优化策略

在真实 Java 项目中，实现有向图邻接表时需考虑以下优化点。

第一，避免频繁扩容。如果预估顶点数量，应在初始化时指定容量，例如：

```java
new ArrayList<>(expectedSize);
```

第二，使用基本类型优化。若顶点为整数，可避免使用包装类减少内存开销。

第三，考虑并发场景。如果邻接表在多线程环境中访问，可使用 `ConcurrentHashMap` 或加锁机制保证安全。

第四，考虑内存占用。对于超大规模图，可以使用压缩存储结构，例如 CSR（Compressed Sparse Row），其原理仍基于邻接表思想。

**工程中的有向图邻接表不仅仅是算法结构，更是系统架构的一部分。**

## 七、常见问题与错误排查

在实现有向图邻接表时，常见错误包括：

第一，忘记初始化内部列表，导致空指针异常。

第二，混淆有向图与无向图。在无向图中需添加两条边。

第三，错误处理索引越界问题。

第四，递归 DFS 可能导致栈溢出。在大规模图中建议使用非递归实现。

在复杂系统中，建议对图结构增加日志或可视化工具，以便排查依赖关系错误。

## 八、未来趋势与总结

随着大数据与复杂系统的发展，有向图结构的应用场景不断扩大。图数据库、推荐系统、依赖分析、知识图谱等领域都大量使用图结构模型。

邻接表作为经典图存储方式，在 Java 中仍具有重要价值。未来的发展趋势包括：

- 更高效的图存储压缩结构
- 与分布式系统结合
- 图计算框架集成

**总的来看，有向图邻接表是 Java 图算法实现的核心基础结构，具有高效率、低空间消耗和良好的扩展性。**掌握其实现方式与优化技巧，对于提升算法能力与系统设计能力具有长期价值。

在实际开发中，应根据数据规模、并发需求与算法复杂度选择合理的邻接表实现方式，从而构建高效、可维护的图结构系统。

参考与资料来源  
1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms, 3rd Edition, MIT Press, 2009.  
2. Sedgewick, R., Wayne, K. Algorithms, 4th Edition, Addison-Wesley, 2011.

在Java中，可以使用数组或HashMap结合链表（如LinkedList）来表示有向图的邻接表。具体做法是为每个顶点维护一个邻居列表，列表中存储该顶点指向的所有顶点。这样可以方便地添加、遍历边，且空间效率较高。

使用Java集合实现有向图的邻接表

我想用Java实现有向图的邻接表存储方式，应该选择什么数据结构来表示节点和边？

如何在Java中表示有向图的邻接表结构？

可以定义一个邻接表为List<List<Integer>>类型，每个下标对应图的一个顶点，内部列表存储其出边指向的邻居顶点。例如：

List<List<Integer>> adjacencyList = new ArrayList<>();
for(int i = 0; i < vertexCount; i++) {
    adjacencyList.add(new LinkedList<>());
}
adjacencyList.get(source).add(destination); // 添加一条从source指向destination的边

示例代码构建有向图邻接表

能否给出一个简单示例代码，展示如何在Java中构建有向图邻接表并添加边？

Java代码中如何构建一个有向图的邻接表？

遍历邻接表时，可以依次访问每个顶点对应的邻居列表，使用增强for循环遍历顶点和其所有出边节点。这样访问邻居节点的时间复杂度较低，适合进行深度优先或广度优先搜索等操作。

遍历有向图邻接表的常用方法

在用Java实现有向图邻接表后，怎样高效地访问所有边和邻居节点？

有向图的邻接表如何高效进行遍历？

PingCodeDocs

有向图的邻接表在Java中通常通过列表或映射结构为每个顶点维护出边集合，空间复杂度为O(V+E)，适合稀疏图与算法实现。相比邻接矩阵，邻接表在内存占用和遍历效率上更具优势。开发中可根据顶点特性选择ArrayList或Map结构，并结合DFS、拓扑排序等算法实现复杂依赖分析。掌握邻接表实现与优化方法，有助于构建高性能图结构系统。

有向图的邻接表java