Java图结构实现：邻接矩阵存储边关系

本文深入讲解了如何在Java中使用邻接矩阵（二维布尔数组）高效、清晰地实现图结构，重点解决了节点与边关系的存储、快速连通性查询、有向边管理等核心问题，并强调了索引映射机制、Node类必须重写equals和hashCode以确保逻辑正确性、边界校验与异常防护等关键实践细节；该方案特别适合节点数量相对固定、需高频判断两点连通性的场景，兼具简洁性、可读性与性能优势，为后续图的可视化渲染和算法扩展奠定了坚实可靠的基础。

本文介绍如何在 Java 中通过邻接矩阵（二维布尔数组）高效、清晰地表示图的节点与边关系，支持快速查询和连接操作，并涵盖索引映射、`equals`/`hashCode` 重写等关键实践要点。

在构建图结构（尤其是后续需可视化展示的图）时，核心挑战之一是如何准确、高效地存储节点之间的连接关系（即边）。虽然 Map>（邻接表）或自定义 Pair 类看似直观，但对初学者而言，邻接矩阵（Adjacency Matrix）是一种逻辑清晰、易于理解且性能可控的首选方案——尤其适用于节点数量相对固定、需频繁判断两点是否连通的场景。

✅ 推荐方案：基于索引的邻接矩阵

假设图中最多有 n 个节点，我们可采用以下结构：

public class Graph {
    private final Node[] nodes;          // 节点数组，每个 Node 关联唯一索引
    private final boolean[][] adjacent;  // 邻接矩阵：adjacent[i][j] 表示 i→j 是否存在有向边

    public Graph(int n) {
        this.nodes = new Node[n];
        this.adjacent = new boolean[n][n]; // 初始化为全 false
    }

    // 注册节点（按顺序分配索引）
    public void addNode(int index, Node node) {
        if (index >= 0 && index < nodes.length) {
            nodes[index] = node;
        } else {
            throw new IllegalArgumentException("Invalid index: " + index);
        }
    }

    // 建立有向边：从节点 a 到节点 b
    public void connect(Node a, Node b) {
        int idxA = indexOf(a);
        int idxB = indexOf(b);
        if (idxA == -1 || idxB == -1) {
            throw new IllegalArgumentException("Node not found in graph");
        }
        adjacent[idxA][idxB] = true;
    }

    // 查询两节点间是否存在有向边
    public boolean areConnected(Node a, Node b) {
        int idxA = indexOf(a);
        int idxB = indexOf(b);
        return idxA != -1 && idxB != -1 && adjacent[idxA][idxB];
    }

    // 根据节点对象查找其索引（需重写 equals！）
    private int indexOf(Node target) {
        if (target == null) return -1;
        for (int i = 0; i < nodes.length; i++) {
            if (nodes[i] != null && nodes[i].equals(target)) {
                return i;
            }
        }
        return -1;
    }
}

⚠️ 关键注意事项

1. 必须重写 equals() 和 hashCode()
   默认的 Object.equals() 仅比较引用地址，会导致 indexOf() 失效。应在 Node 类中明确定义“相等”逻辑（例如基于 ID 或 data）：

   @Override
   public boolean equals(Object o) {
       if (this == o) return true;
       if (o == null || getClass() != o.getClass()) return false;
       Node node = (Node) o;
       return ID == node.ID && Objects.equals(data, node.data);
   }
   
   @Override
   public int hashCode() {
       return Objects.hash(ID, data);
   }

2. 边界与异常防护
   所有涉及索引的操作（如 connect()、areConnected()）应校验索引有效性，推荐抛出 IllegalArgumentException 或自定义 GraphException，避免静默失败。

3. 扩展性提示

   • 若节点数量动态变化，可用 List 替代固定数组，并用 List> 模拟动态邻接矩阵；
   • 若需权重（如距离、成本），将 boolean[][] 升级为 int[][]、double[][] 或自定义 Edge 对象矩阵；
   • 对于稀疏图（边远少于节点平方），邻接表（Map>）更省内存。

? 小结

邻接矩阵以空间换时间，提供 O(1) 的连通性查询和 O(1) 的边插入，配合节点索引管理与正确的 equals 实现，即可构建健壮、可维护的图数据结构。此基础模型可无缝对接 JavaFX/Swing 等 GUI 框架，为后续图形化渲染（如自动布局、连线绘制）提供可靠的数据支撑。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。