Java数组实现邻接矩阵判断顶点连通性

本文深入浅出地介绍了如何在Java中利用二维布尔数组高效实现图的邻接矩阵表示，并聚焦于顶点间直接连通性的快速判断——通过简洁的`isConnected(u, v)`方法，仅需一次数组索引访问即可判定两顶点是否存在直连边；同时清晰对比了无向图（对称矩阵）、有向图（方向敏感）和带权图（整型矩阵+无效值约定）的不同处理方式，并辅以可运行的代码示例与实用建议，如顶点编号规范、稀疏图优化提醒及扩展方向，帮助开发者夯实图基础、避开常见陷阱。

在 Java 中，可以用二维布尔数组或整型数组模拟图的邻接矩阵。若两个顶点 u 和 v 直接相连（即存在一条边），只需检查矩阵中对应位置是否为 true 或非零值即可。

邻接矩阵的基本结构

邻接矩阵是一个 n × n 的二维数组（n 为顶点数），索引代表顶点编号（通常从 0 开始）。矩阵元素 matrix[u][v] 表示顶点 u 到 v 是否有边：

• 无向图：矩阵对称，matrix[u][v] == matrix[v][u]
• 有向图：不对称，需按边方向赋值
• 权值图：用 int[][] 存储权重，0 或 -1 表示无边（需约定无效值）
• 简单连通判断：用 boolean[][] 更直观、节省空间

创建邻接矩阵并添加边

以下是一个基于顶点数量初始化、支持添加无向边的示例：

public class Graph {
    private final int n;
    private final boolean[][] matrix;

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

    // 添加无向边 u-v
    public void addEdge(int u, int v) {
        if (isValid(u) && isValid(v)) {
            matrix[u][v] = true;
            matrix[v][u] = true;
        }
    }

    // 判断顶点 u 和 v 是否直接相连
    public boolean isConnected(int u, int v) {
        return isValid(u) && isValid(v) && matrix[u][v];
    }

    private boolean isValid(int x) {
        return x >= 0 && x 

<h3>使用示例与判断逻辑</h3>
<p>假设构建一个含 4 个顶点（0–3）的无向图，添加边 (0,1)、(1,2)、(2,3)：</p>
<pre class="brush:java;toolbar:false;">Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 3);

System.out.println(g.isConnected(0, 1)); // true
System.out.println(g.isConnected(0, 2)); // false（不相邻，需经 1 中转）
System.out.println(g.isConnected(1, 3)); // false

注意：isConnected 只判断是否存在直接边，不涉及路径搜索。若需判断是否连通（可达），需配合 BFS/DFS。

小提示：边界与扩展建议

• 顶点编号建议统一从 0 开始，避免数组越界
• 若顶点名是字符串（如 "A", "B"），可用 HashMap 做映射
• 稀疏图慎用邻接矩阵（空间复杂度 O(n²)），优先考虑邻接表
• 支持删除边？只需设 matrix[u][v] = matrix[v][u] = false

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~