java代码怎样用邻接表实现图结构 java代码图结构的邻接表实现方法

答案：Java中邻接表通过Map存储顶点及其邻居列表，适合稀疏图，空间复杂度O(V+E)，扩展支持带权或有向图，需注意顶点映射、线程安全及删除操作的性能问题。

Java中，图的邻接表实现核心在于用一个数据结构（通常是

Map

或

List

的数组）来映射每个顶点，其值则是一个列表，存储着所有与该顶点直接相连的邻居。这就像给每个节点发了一张名片，上面列着它所有朋友的名字，简单直接，效率也挺高。

解决方案

实现图的邻接表结构，我们通常会创建一个类来封装这个逻辑。我个人习惯用

HashMap

来存储顶点和它们的邻居列表，因为这样可以灵活地使用任何类型的对象作为顶点标识，不局限于整数。

import java.util.*;// 假设我们用整数代表图的顶点，当然你也可以用String或者自定义对象public class AdjacencyListGraph {    // 核心数据结构：Map的键是顶点，值是该顶点所有邻居的列表    private Map<Integer, List> adj;     public AdjacencyListGraph() {        this.adj = new HashMap();    }    /**     * 添加一个顶点到图中。     * 如果顶点已经存在，则不进行任何操作。     */    public void addVertex(int vertex) {        // computeIfAbsent 是个很方便的方法，如果键不存在就创建并放入一个新列表        adj.computeIfAbsent(vertex, k -> new ArrayList());        // System.out.println("添加顶点: " + vertex); // 调试信息，实际应用中可能不需要    }    /**     * 添加一条边到图中。     * 这里的实现是针对无向图的，所以会在两个方向上都添加连接。     * 如果是带权图或有向图，需要对这里的List和逻辑进行调整。     */    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 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> 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

。但带权图需要知道边上的“重量”或“成本”。这时候，我们不能只存邻居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> 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）影响可就大了。理解了这一点，你会发现图的很多复杂算法，其实都是基于这些基本表示方法的变种。