Java加权图入门教程（从零开始构建带权重的图数据结构）

Java中如何表示加权图？

常见的图表示方法有两种：邻接矩阵和邻接表。对于稀疏图（边数远小于节点数平方），邻接表更节省空间，因此我们采用它来实现。

我们将使用以下结构：

• Edge 类：表示一条带权重的边
• WeightedGraph 类：使用 Map<String, List<Edge>> 存储邻接表

1. 定义 Edge 类

public class Edge {    String destination; // 目标节点    int weight;         // 边的权重    public Edge(String destination, int weight) {        this.destination = destination;        this.weight = weight;    }    @Override    public String toString() {        return destination + "(" + weight + ")";    }}

2. 实现 WeightedGraph 类

import java.util.*;public class WeightedGraph {    // 使用邻接表：节点名 -> 邻居列表    private Map<String, List<Edge>> adjList;    public WeightedGraph() {        adjList = new HashMap<>();    }    // 添加节点（如果不存在）    public void addVertex(String vertex) {        adjList.putIfAbsent(vertex, new ArrayList<>());    }    // 添加带权重的边（无向图）    public void addEdge(String src, String dest, int weight) {        // 确保两个节点都存在        addVertex(src);        addVertex(dest);                // 添加双向边        adjList.get(src).add(new Edge(dest, weight));        adjList.get(dest).add(new Edge(src, weight));    }    // 打印整个图    public void printGraph() {        for (String vertex : adjList.keySet()) {            System.out.print(vertex + " -> ");            for (Edge edge : adjList.get(vertex)) {                System.out.print(edge + " ");            }            System.out.println();        }    }}

测试我们的加权图

现在我们创建一个简单的图并测试它：

public class Main {    public static void main(String[] args) {        WeightedGraph graph = new WeightedGraph();                graph.addEdge("A", "B", 5);        graph.addEdge("B", "C", 3);        graph.addEdge("A", "C", 10);                graph.printGraph();    }}

输出结果：

A -> B(5) C(10) B -> A(5) C(3) C -> B(3) A(10)

扩展：最短路径算法（Dijkstra）

加权图的一个经典应用是求最短路径。Dijkstra 算法是解决单源最短路径问题的常用方法。虽然完整实现较复杂，但理解加权图是学习该算法的基础。

掌握 Java加权图 的构建后，你就可以进一步探索 最短路径算法、最小生成树（如 Prim 或 Kruskal 算法）等高级主题。

总结

本教程详细讲解了如何用 Java 实现一个基于 邻接表 的加权图数据结构。我们定义了 Edge 和 WeightedGraph 类，并通过简单示例验证了其功能。这是学习图论算法（如 Dijkstra）的重要第一步。

无论你是准备面试，还是开发路径规划系统，理解 图数据结构 都至关重要。希望这篇面向初学者的教程能帮你打下坚实基础！