Java 图形结构中节点与边的高效存储方案：从邻接矩阵到动态图表示

本文介绍在 java 中如何科学存储图的节点与边关系，重点讲解基于索引的邻接矩阵实现、节点唯一性保障（equals/hashcode）、边界防护机制，并延伸至动态扩展场景（如 list>），兼顾性能与可维护性。

在构建可可视化图结构（如图形界面中的拓扑图）时，核心挑战之一是如何准确、高效且可扩展地表示节点（vertices）之间的连接关系（edges）。虽然 Map>（邻接表）或自定义 Pair 是常见思路，但对初学者而言，邻接矩阵（Adjacency Matrix）因其逻辑清晰、查询 O(1)、易于理解，是更稳妥的起点——尤其当节点总数相对固定或可预估时。

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

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

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

    public Graph(int n) {
        this.nodes = new Node[n];
        this.adjacent = new boolean[n][n];
    }

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

    // 建立有向边：from → to
    public void connect(int from, int to) {
        validateIndex(from, to);
        adjacent[from][to] = true;
    }

    // 查询两点是否连通（有向）
    public boolean areConnected(int from, int to) {
        validateIndex(from, to);
        return adjacent[from][to];
    }

    // 安全校验索引合法性
    private void validateIndex(int... indices) {
        for (int idx : indices) {
            if (idx < 0 || idx >= nodes.length) {
                throw new IllegalArgumentException("Invalid node index: " + idx);
            }
        }
    }
}

配合 Node 类，必须重写 equals() 和 hashCode()，否则 indexOf() 或 Map 查找将失效（默认引用比较）：

public class Node {
    private final String data;
    private final int id;

    public Node(String data, int id) {
        this.data = data;
        this.id = id;
    }

    // 关键：按业务语义判断相等性（如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(data, id);
    }

    // getter 省略...
}

? 支持按节点对象查询（非索引）

若需通过 Node 实例而非索引调用 areConnected(Node a, Node b)，可添加辅助方法：

public 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;
}

public boolean areConnected(Node a, Node b) {
    int i = indexOf(a);
    int j = indexOf(b);
    if (i == -1 || j == -1) return false;
    return areConnected(i, j); 
// 复用索引版
}

⚠️ 注意事项与进阶建议

• 方向性：上述矩阵默认表示有向图。若需无向图，连接时应同步设置 adjacent[i][j] = adjacent[j][i] = true。
• 内存权衡：邻接矩阵空间复杂度为 O(n²)，适合稠密图或节点数可控（如 ≤ 1000）场景；稀疏图推荐邻接表（Map>）。
• 动态扩展：若节点数未知或频繁增删，可用 List> 替代二维数组：

  private final List> dynamicAdjacent = new ArrayList<>();
  // 初始化：for (int i = 0; i < n; i++) dynamicAdjacent.add(new ArrayList<>(Collections.nCopies(n, false)));

• 权重支持：将 boolean[][] 升级为 int[][]（距离）、double[][]（坐标距离）或自定义 Edge 对象数组，即可支持加权图。
• GUI 集成提示：在 Swing/JavaFX 中，每个 Node 可额外封装 x, y, width, height 等绘图属性，Graph 类负责维护逻辑连接，渲染层独立处理布局与连线绘制。

综上，邻接矩阵是理解图存储的基石方案。它简洁、健壮、易调试，配合合理的封装与防御式编程，能为后续图形化界面开发提供坚实的数据支撑。