Java边列表详解（从零开始掌握图的邻接表存储结构）

什么是边列表（邻接表）？

边列表（Edge List）和邻接表（Adjacency List）虽然名称相似，但在实际使用中，邻接表更为常见。邻接表通过为图中的每个顶点维护一个“邻居列表”来表示图的连接关系。

例如，对于一个有向图：

• A → B
• A → C
• B → C

其邻接表表示为：

A: [B, C]B: [C]C: []

为什么使用邻接表？

相比于邻接矩阵，邻接表在存储稀疏图（即边数远小于顶点数平方的图）时更加节省空间。同时，它便于遍历某个顶点的所有邻接点，非常适合用于实现Java图算法如深度优先搜索（DFS）、广度优先搜索（BFS）等。

用Java实现邻接表

在Java中，我们可以使用 HashMap 和 ArrayList 来构建邻接表。下面是一个完整的示例：

import java.util.*;public class Graph {    // 使用 HashMap 存储每个顶点及其邻接点列表    private Map<String, List<String>> adjList;    public Graph() {        adjList = new HashMap<>();    }    // 添加顶点    public void addVertex(String vertex) {        adjList.putIfAbsent(vertex, new ArrayList<>());    }    // 添加边（无向图）    public void addEdge(String v1, String v2) {        // 确保两个顶点都存在        addVertex(v1);        addVertex(v2);                // 无向图：双向添加        adjList.get(v1).add(v2);        adjList.get(v2).add(v1);    }    // 打印邻接表    public void printGraph() {        for (String vertex : adjList.keySet()) {            System.out.println(vertex + " -> " + adjList.get(vertex));        }    }    public static void main(String[] args) {        Graph g = new Graph();        g.addEdge("A", "B");        g.addEdge("A", "C");        g.addEdge("B", "C");        g.printGraph();    }}

运行上述代码，输出结果为：

A -> [B, C]B -> [A, C]C -> [A, B]

注意：上面的例子实现的是无向图。如果你需要实现有向图，只需在 addEdge 方法中只添加单向边即可。

扩展：带权重的边

在实际应用中，图的边往往带有权重（如距离、成本等）。这时我们可以定义一个内部类来表示带权边：

class WeightedEdge {    String target;    int weight;    public WeightedEdge(String target, int weight) {        this.target = target;        this.weight = weight;    }    @Override    public String toString() {        return target + "(" + weight + ")";    }}// 修改邻接表类型private Map<String, List<WeightedEdge>> weightedAdjList;

总结

通过本教程，你已经掌握了如何在Java中使用邻接表来表示图。这种结构是学习更高级Java图算法（如Dijkstra最短路径、Kruskal最小生成树等）的基础。记住，Java边列表（邻接表）不仅节省内存，而且操作灵活，是处理图问题的首选方式之一。

希望这篇关于Java邻接表的教程对你有所帮助！动手实践一下吧，编程能力就是在一次次敲代码中提升的。