答案：Java中邻接表通过Map存储顶点及其邻居列表，适合稀疏图，空间复杂度O(V+E)，扩展支持带权或有向图，需注意顶点映射、线程安全及删除操作的性能问题。
Java中，图的邻接表实现核心在于用一个数据结构（通常是
Map
或
List
的数组）来映射每个顶点，其值则是一个列表，存储着所有与该顶点直接相连的邻居。这就像给每个节点发了一张名片，上面列着它所有朋友的名字，简单直接，效率也挺高。
解决方案
实现图的邻接表结构，我们通常会创建一个类来封装这个逻辑。我个人习惯用
HashMap
来存储顶点和它们的邻居列表，因为这样可以灵活地使用任何类型的对象作为顶点标识，不局限于整数。
import java.util.*; // 假设我们用整数代表图的顶点，当然你也可以用String或者自定义对象 public class AdjacencyListGraph { // 核心数据结构：Map的键是顶点，值是该顶点所有邻居的列表 private Map<Integer, List<Integer>> adj; public AdjacencyListGraph() { this.adj = new HashMap<>(); } /** * 添加一个顶点到图中。 * 如果顶点已经存在，则不进行任何操作。 */ public void addVertex(int vertex) { // computeIfAbsent 是个很方便的方法，如果键不存在就创建并放入一个新列表 adj.computeIfAbsent(vertex, k -> new ArrayList<>()); // System.out.println("添加顶点: " + vertex); // 调试信息，实际应用中可能不需要 } /** * 添加一条边到图中。 * 这里的实现是针对无向图的，所以会在两个方向上都添加连接。 * 如果是带权图或有向图，需要对这里的List<Integer>和逻辑进行调整。 */ public void addEdge(int source, int destination) { // 确保源和目标顶点都已存在于图中 addVertex(source); addVertex(destination); // 为源顶点添加目标邻居 adj.get(source).add(destination); // 对于无向图，反方向也需要添加连接 adj.get(destination).add(source); // System.out.println("添加边: " + source + " -- " + destination); // 调试信息 } /** * 获取指定顶点的所有邻居。 * 如果顶点不存在，则返回一个空列表。 */ public List<Integer> getNeighbors(int vertex) { return adj.getOrDefault(vertex, Collections.emptyList()); } /** * 检查两个顶点之间是否存在边。 */ public boolean hasEdge(int source, int destination) { // 确保源顶点存在且其邻居列表中包含目标顶点 return adj.containsKey(source) && adj.get(source).contains(destination); } /** * 打印整个图的邻接表结构，方便查看。 */ public void printGraph() { System.out.println("n--- 图结构 (邻接表表示) ---"); for (Map.Entry<Integer, List<Integer>> entry : adj.entrySet()) { System.out.print("顶点 " + entry.getKey() + " 的邻居: "); System.out.println(entry.getValue()); } System.out.println("--------------------------"); } public static void main(String[] args) { AdjacencyListGraph graph = new AdjacencyListGraph(); // 添加一些顶点 graph.addVertex(0); graph.addVertex(1); graph.addVertex(2); graph.addVertex(3); graph.addVertex(4); // 添加一些边 graph.addEdge(0, 1); graph.addEdge(0, 4); graph.addEdge(1, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); graph.addEdge(2, 3); graph.addEdge(3, 4); // 打印图结构 graph.printGraph(); // 查询邻居 System.out.println("顶点 1 的邻居: " + graph.getNeighbors(1)); // 预期: [0, 2, 3, 4] System.out.println("顶点 5 的邻居 (不存在): " + graph.getNeighbors(5)); // 预期: [] // 检查边是否存在 System.out.println("0和1之间有边吗? " + graph.hasEdge(0, 1)); // 预期: true System.out.println("0和2之间有边吗? " + graph.hasEdge(0, 2)); // 预期: false } }
这段代码提供了一个基本的无向无权图的邻接表实现。它涵盖了添加顶点、添加边、获取邻居以及打印图结构这些核心功能。在我看来，这种结构直观且易于扩展。
邻接表与邻接矩阵：何时选择邻接表更优？
选择邻接表还是邻接矩阵，这真的是一个经典问题，也是我每次设计图结构时都会思考的。说白了，这取决于你的图是什么样的，以及你主要想做什么操作。
立即学习“Java免费学习笔记（深入）”；
邻接矩阵，它用一个二维数组
adj[V][V]
来表示图，
adj[i][j]
为1表示i到j有边，0表示没有。这种方式直观，判断两点间是否有边是O(1)的，很快。但是，它的空间复杂度是O(V^2)，V是顶点数。想象一下，如果你的图有10000个节点，那矩阵就是1亿个单元格，哪怕是稀疏图（边很少），也得占用这么多空间。
而邻接表呢，它的空间复杂度是O(V+E)，V是顶点数，E是边数。对于稀疏图（比如社交网络，每个人只认识少数几个人），E远小于V^2，邻接表在空间上就显得非常有优势了。比如10000个节点，平均每个节点有100条边，总边数也就100万，这比1亿小太多了。此外，遍历一个顶点的所有邻居时，邻接表只需要遍历该顶点的邻接列表，时间复杂度是O(degree(V))，而邻接矩阵需要遍历一整行，是O(V)。显然，邻接表在查找邻居这块也更高效。
所以，我个人觉得，如果你的图是稀疏的，或者你更频繁地进行“找出某个节点的所有邻居”这样的操作，那么邻接表绝对是首选。它能帮你省下大量的内存，同时在许多常用操作上表现更优。但如果你图的密度很高，边数接近V^2，或者你特别需要O(1)判断任意两点是否有边，那邻接矩阵可能更合适，但这种情况在实际应用中并不那么常见。
如何在邻接表中表示带权图或有向图？
在邻接表的基础上表示带权图或有向图，其实并不复杂，主要是对邻接列表中存储的元素做些小调整。
表示带权图 (Weighted Graph): 无权图的邻接列表里直接存的是邻居顶点的ID，比如
List<Integer>
。但带权图需要知道边上的“重量”或“成本”。这时候，我们不能只存邻居ID了，得把权重也带上。最常见的做法是定义一个
Edge
（边）类，把邻居顶点和权重都封装进去。
// 定义一个边类，包含目标顶点和权重 class Edge { int destination; int weight; public Edge(int destination, int weight) { this.destination = destination; this.weight = weight; } @Override public String toString() { return "(" + destination + ", weight=" + weight + ")"; } } // 那么，你的邻接表类型就会变成这样： // private Map<Integer, List<Edge>> adj; // addEdge 方法也会相应调整： public void addWeightedEdge(int source, int destination, int weight) { addVertex(source); addVertex(destination); adj.get(source).add(new Edge(destination, weight)); // 如果是无向带权图，反向也需要添加 // adj.get(destination).add(new Edge(source, weight)); }
这样，当你获取一个顶点的邻居列表时，你得到的是
List<Edge>
，通过遍历这个列表，你不仅知道有哪些邻居，还能知道到达这些邻居的权重是多少。这种方式非常灵活，我觉得是处理带权图最自然的方式。
表示有向图 (Directed Graph): 有向图的表示就更简单了。无向图之所以在
addEdge
时要双向添加（
source -> destination
和
destination -> source
），是因为边是双向可达的。而有向图，顾名思义，边是有方向的，只能从源顶点到目标顶点单向通行。
所以，实现有向图的邻接表，你只需要在
addEdge
方法中，只添加从源到目标的连接即可，不需要反向添加。
// 假设是无权有向图 public void addDirectedEdge(int source, int destination) { addVertex(source); addVertex(destination); adj.get(source).add(destination); // 只添加单向连接 } // 如果是有向带权图，结合上面的Edge类： public void addDirectedWeightedEdge(int source, int destination, int weight) { addVertex(source); addVertex(destination); adj.get(source).add(new Edge(destination, weight)); // 同样只添加单向连接 }
就这么点区别，但对图的遍历算法（比如DFS、BFS）以及路径查找（比如Dijkstra、Floyd-Warshall）影响可就大了。理解了这一点，你会发现图的很多复杂算法，其实都是基于这些基本表示方法的变种。
邻接表在实际应用中可能遇到的挑战与优化策略
邻接表虽然好用，但在实际应用中，尤其当图的规模变得非常大，或者有特殊需求时，也会遇到一些挑战。我个人在处理这些问题时，有一些思考和实践经验。
1. 顶点ID的管理与映射： 如果你的顶点不是简单的整数（比如是用户ID字符串、复杂的对象），你不能直接把它们作为
Map
的键或者
List
的元素。你可能需要一个额外的映射层。 一种常见做法是维护一个
Map<Object, Integer>
来将实际的顶点对象映射到一个内部的整数ID，然后邻接表仍然使用整数ID。这样既保证了邻接表的紧凑性，又提供了灵活的顶点表示。 或者，如果你对性能要求不是极致，且顶点对象本身就适合作为
Map
的键（比如
String
），那么直接使用
Map<String, List<String>>
或者
Map<YourCustomObject, List<YourCustomObject>>
也是可以的。后者在哈希和比较上可能会有轻微开销，但代码会更直观。我通常会根据具体场景来权衡。
2. 并发访问与线程安全： 在多线程环境下，如果多个线程同时对图结构进行修改（比如添加或删除边、顶点），那么默认的
HashMap
和
ArrayList
都不是线程安全的。这可能会导致数据不一致或运行时错误。 解决方案通常有几种：
- 外部同步： 在所有修改图结构的操作外部加上锁（
synchronized
块或
ReentrantLock
）。这最简单，但可能限制并发性。
- 使用线程安全集合： 将
HashMap
替换为
ConcurrentHashMap
，将
ArrayList
替换为
CopyOnWriteArrayList
或使用
Collections.synchronizedList()
包装。
ConcurrentHashMap
在并发读写方面表现很好，但
CopyOnWriteArrayList
在写操作频繁时性能可能不佳，因为它每次修改都会复制底层数组。
- 不可变图： 如果图结构一旦构建就不再修改，那么就可以完全避免并发问题。 但说实话，大部分图算法本身都是单线程执行的，只有在构建或更新图的阶段才需要考虑并发。
3. 删除顶点或边： 删除边相对简单，从对应顶点的邻接列表中移除目标顶点即可。但删除一个顶点就有点儿麻烦了。你不仅要从
adj
这个
Map
中移除这个顶点本身，还得遍历所有其他顶点的邻接列表，把指向这个被删除顶点的边也一并移除。这个操作在图很大的时候，可能会有不小的开销，因为它可能需要遍历整个图。
4. 内存碎片与性能：
ArrayList
在添加元素时，如果容量不足会进行扩容，这涉及
评论（已关闭）
评论已关闭