Java图结构邻接表实现教程

本文深入解析了Java中利用邻接表实现图结构的方法。邻接表通过`Map`存储顶点及其邻居列表，尤其适用于表示稀疏图，其空间复杂度为O(V+E)。代码示例展示了如何使用`HashMap`实现邻接表，并提供了添加顶点、边、查询邻居等核心功能。同时，文章探讨了邻接表与邻接矩阵的选择，以及如何在邻接表中表示带权图和有向图。此外，还讨论了实际应用中可能遇到的挑战，如顶点ID管理、线程安全和删除操作的性能问题，并提出了相应的优化策略，为开发者提供了全面的解决方案和深入的实践指导。

答案：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
    }
}

这段代码提供了一个基本的无向无权图的邻接表实现。它涵盖了添加顶点、添加边、获取邻居以及打印图结构这些核心功能。在我看来，这种结构直观且易于扩展。

邻接表与邻接矩阵：何时选择邻接表更优？

选择邻接表还是邻接矩阵，这真的是一个经典问题，也是我每次设计图结构时都会思考的。说白了，这取决于你的图是什么样的，以及你主要想做什么操作。

邻接矩阵，它用一个二维数组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。但带权图需要知道边上的“重量”或“成本”。这时候，我们不能只存邻居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，通过遍历这个列表，你不仅知道有哪些邻居，还能知道到达这些邻居的权重是多少。这种方式非常灵活，我觉得是处理带权图最自然的方式。

表示有向图 (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来将实际的顶点对象映射到一个内部的整数ID，然后邻接表仍然使用整数ID。这样既保证了邻接表的紧凑性，又提供了灵活的顶点表示。 或者，如果你对性能要求不是极致，且顶点对象本身就适合作为Map的键（比如String），那么直接使用Map>或者Map>也是可以的。后者在哈希和比较上可能会有轻微开销，但代码会更直观。我通常会根据具体场景来权衡。

2. 并发访问与线程安全： 在多线程环境下，如果多个线程同时对图结构进行修改（比如添加或删除边、顶点），那么默认的HashMap和ArrayList都不是线程安全的。这可能会导致数据不一致或运行时错误。 解决方案通常有几种：

• 外部同步： 在所有修改图结构的操作外部加上锁（synchronized块或ReentrantLock）。这最简单，但可能限制并发性。
• 使用线程安全集合： 将HashMap替换为ConcurrentHashMap，将ArrayList替换为CopyOnWriteArrayList或使用Collections.synchronizedList()包装。ConcurrentHashMap在并发读写方面表现很好，但CopyOnWriteArrayList在写操作频繁时性能可能不佳，因为它每次修改都会复制底层数组。
• 不可变图： 如果图结构一旦构建就不再修改，那么就可以完全避免并发问题。 但说实话，大部分图算法本身都是单线程执行的，只有在构建或更新图的阶段才需要考虑并发。

3. 删除顶点或边： 删除边相对简单，从对应顶点的邻接列表中移除目标顶点即可。但删除一个顶点就有点儿麻烦了。你不仅要从adj这个Map中移除这个顶点本身，还得遍历所有其他顶点的邻接列表，把指向这个被删除顶点的边也一并移除。这个操作在图很大的时候，可能会有不小的开销，因为它可能需要遍历整个图。

4. 内存碎片与性能：ArrayList在添加元素时，如果容量不足会进行扩容，这涉及

理论要掌握，实操不能落！以上关于《Java图结构邻接表实现教程》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！