深入理解图数据结构（Java语言图数据结构入门与实战指南）

什么是图？

图（Graph）由顶点（Vertex，也称节点）和边（Edge）组成。边可以是有向的（如 A → B）或无向的（如 A — B）。根据边是否有权重，图又可分为带权图和无权图。

图的两种主要表示方法

在 Java 中，我们通常使用以下两种方式来表示图：

• 邻接矩阵（Adjacency Matrix）：用二维数组表示，适合稠密图。
• 邻接表（Adjacency List）：用链表或 ArrayList 的集合表示，适合稀疏图，节省空间。

对于大多数实际应用，邻接表实现更为常用，因此本教程将重点讲解它。

使用 Java 实现邻接表图结构

下面是一个简单的无向无权图的 Java 实现：

import java.util.*;public class Graph {    private Map<Integer, List<Integer>> adjList;    // 构造函数    public Graph() {        adjList = new HashMap<>();    }    // 添加顶点    public void addVertex(int vertex) {        adjList.putIfAbsent(vertex, new ArrayList<>());    }    // 添加边（无向图）    public void addEdge(int src, int dest) {        // 确保两个顶点都存在        addVertex(src);        addVertex(dest);                // 添加双向连接        adjList.get(src).add(dest);        adjList.get(dest).add(src);    }    // 打印图    public void printGraph() {        for (Map.Entry<Integer, List<Integer>> entry : adjList.entrySet()) {            System.out.println("顶点 " + entry.getKey() + ": " + entry.getValue());        }    }}

图的遍历：深度优先搜索（DFS）与广度优先搜索（BFS）

掌握了图的构建后，下一步是学会如何遍历它。常见的图遍历算法包括 DFS 和 BFS。

深度优先搜索（DFS）示例

public void dfs(int startVertex) {    Set<Integer> visited = new HashSet<>();    dfsHelper(startVertex, visited);}private void dfsHelper(int vertex, Set<Integer> visited) {    visited.add(vertex);    System.out.print(vertex + " ");        for (int neighbor : adjList.getOrDefault(vertex, new ArrayList<>())) {        if (!visited.contains(neighbor)) {            dfsHelper(neighbor, visited);        }    }}

广度优先搜索（BFS）示例

public void bfs(int startVertex) {    Set<Integer> visited = new HashSet<>();    Queue<Integer> queue = new LinkedList<>();        visited.add(startVertex);    queue.add(startVertex);        while (!queue.isEmpty()) {        int current = queue.poll();        System.out.print(current + " ");                for (int neighbor : adjList.getOrDefault(current, new ArrayList<>())) {            if (!visited.contains(neighbor)) {                visited.add(neighbor);                queue.add(neighbor);            }        }    }}

完整测试示例

public class Main {    public static void main(String[] args) {        Graph g = new Graph();                g.addEdge(0, 1);        g.addEdge(0, 2);        g.addEdge(1, 2);        g.addEdge(2, 3);                System.out.println("图的邻接表表示：");        g.printGraph();                System.out.print("\nDFS 从顶点 0 开始: ");        g.dfs(0);                System.out.print("\nBFS 从顶点 0 开始: ");        g.bfs(0);    }}

总结

通过本教程，你已经学会了：

• 图的基本概念及其在现实中的应用
• 如何使用 Java 实现基于邻接表的图结构
• 两种核心的图遍历算法：DFS 与 BFS
• 完整的代码示例，可直接运行验证

掌握 Java语言图数据结构 是进阶算法学习的重要一步。无论是面试还是实际开发，图的相关知识都极为实用。建议你动手敲一遍代码，加深理解！

关键词回顾：Java图数据结构、图的表示方法、邻接表实现、图遍历算法。