Java实现Graph ADT时二维ArrayList添加元素遇索引越界错误

常见问题排查与修复方案 #

1. 二维ArrayList初始化不匹配顶点数量 #

二维邻接表的外层ArrayList需要和顶点列表的长度严格对应——每添加一个顶点，必须同步为该顶点创建一个空的边列表。如果只初始化外层ArrayList但未填充内层列表，直接访问adjList.get(0)必然触发越界错误。

错误示例：

ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
// 此时adjList为空，直接调用adjList.get(0).add(1)会报错

正确初始化逻辑（添加顶点时同步创建边列表）：

// 存储顶点的一维列表
private ArrayList<String> vertices = new ArrayList<>();
// 存储边的二维邻接表
private ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();

// 添加顶点方法
public void addVertex(String vertex) {
    vertices.add(vertex);
    adjList.add(new ArrayList<>()); // 为新顶点绑定空的边列表
}

2. insertEdge方法缺失索引合法性检查 #

调用insertEdge(v1, v2)时，若v1或v2的索引超过当前顶点总数（即外层ArrayList的长度），会直接触发越界。必须先校验索引范围：

修正后的insertEdge方法：

public void insertEdge(int v1, int v2) {
    // 检查顶点索引是否在合法范围内
    if (v1 < 0 || v1 >= adjList.size() || v2 < 0 || v2 >= adjList.size()) {
        throw new IllegalArgumentException("顶点索引非法");
    }
    // 无向图需添加双向边，有向图仅添加单向
    adjList.get(v1).add(v2);
    adjList.get(v2).add(v1);
}

3. 手动分配行空间的错误方式 #

如果尝试手动为第0行分配空间，不能直接使用set方法（外层列表为空时set会报错），必须先通过add方法将内层列表加入外层：

错误示例：

// 外层列表为空时调用set会触发越界
adjList.set(0, new ArrayList<>());

正确方式：

if (adjList.isEmpty()) {
    adjList.add(new ArrayList<>()); // 先将内层列表加入外层
}
// 之后才能安全访问adjList.get(0)

完整核心代码示例 #

import java.util.ArrayList;

public class GraphADT {
    private ArrayList<String> vertices;
    private ArrayList<ArrayList<Integer>> adjacencyList;

    public GraphADT() {
        vertices = new ArrayList<>();
        adjacencyList = new ArrayList<>();
    }

    // 添加顶点
    public void addVertex(String vertex) {
        vertices.add(vertex);
        adjacencyList.add(new ArrayList<>());
    }

    // 添加无向边
    public void insertEdge(int fromIdx, int toIdx) {
        if (fromIdx < 0 || fromIdx >= vertices.size() 
            || toIdx < 0 || toIdx >= vertices.size()) {
            throw new IndexOutOfBoundsException("顶点索引超出范围");
        }
        adjacencyList.get(fromIdx).add(toIdx);
        adjacencyList.get(toIdx).add(fromIdx);
    }

    // 测试用例
    public static void main(String[] args) {
        GraphADT graph = new GraphADT();
        graph.addVertex("A");
        graph.addVertex("B");
        graph.insertEdge(0, 1);
        System.out.println(graph.adjacencyList.get(0)); // 输出 [1]
    }
}

关键注意事项 #

• 始终保证顶点列表长度与邻接表外层列表长度一致，避免出现“有顶点无对应边列表”的情况。
• 任何访问邻接表内层列表的操作前，必须先校验目标索引的合法性。
• 不要使用set方法修改邻接表的行，除非确认该索引位置已存在元素（即外层列表长度大于目标索引）。

内容的提问来源于stack exchange，提问作者JG98