求助：将邻接矩阵Graph改为ArrayList与泛型的邻接表实现

我来帮你搞定这个改造问题！首先得明确核心问题：你现在的邻接表只存了目标顶点，但原邻接矩阵是带权重的，所以得先给邻接表的每个条目加上权重信息——我们可以用一个内部类来封装边的目标顶点和权重。接下来一步步完成改造：

核心改造思路 #

• 新增内部静态类Edge，封装每条边的目标顶点（泛型E）和权重（double），解决邻接表无法存储权重的问题
• 用List<List<Edge<E>>>替代泛型数组，避免unchecked警告，同时更符合Java集合的使用规范
• 新增List<E> vertices存储所有顶点，对应原代码中索引到顶点名称的映射关系

完整改造代码 #

class Graph<E extends Comparable<E>> {
    // 存储所有顶点，索引对应原代码中的顶点序号i
    private List<E> vertices;
    // 邻接表：每个顶点对应一个边列表，每个边包含目标顶点和权重
    private List<List<Edge<E>>> adjLists;

    /**
     * 构造方法：初始化指定数量的顶点，默认命名为A、B、C...（需E为String类型，或自定义顶点请用另一个构造方法）
     */
    public Graph(int numVertices) {
        vertices = new ArrayList<>(numVertices);
        adjLists = new ArrayList<>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            // 默认生成顶点名称，若E不是String，可替换为自定义顶点生成逻辑
            vertices.add((E) String.format("%c", 'A' + i));
            adjLists.add(new ArrayList<>());
        }
    }

    /**
     * 重载构造方法：允许传入自定义顶点列表
     */
    public Graph(List<E> customVertices) {
        vertices = new ArrayList<>(customVertices);
        adjLists = new ArrayList<>(customVertices.size());
        for (int i = 0; i < customVertices.size(); i++) {
            adjLists.add(new ArrayList<>());
        }
    }

    /**
     * 添加有向边：从索引i的顶点到dest顶点，指定权重
     */
    public void addEdge(int i, E dest, double weight) {
        if (!vertices.contains(dest)) {
            throw new IllegalArgumentException("目标顶点不存在于当前图中");
        }
        adjLists.get(i).add(new Edge<>(dest, weight));
    }

    /**
     * 重载：添加权重为1的有向边，兼容原方法逻辑
     */
    public void addEdge(int i, E dest) {
        addEdge(i, dest, 1.0);
    }

    /**
     * 添加无向边：双向添加权重相同的边
     */
    public void addUndirectedEdge(int i, E dest, double weight) {
        addEdge(i, dest, weight);
        // 找到目标顶点对应的索引，反向添加边
        int destIndex = vertices.indexOf(dest);
        addEdge(destIndex, vertices.get(i), weight);
    }

    /**
     * 重载：添加权重为1的无向边，兼容原方法逻辑
     */
    public void addUndirectedEdge(int i, E dest) {
        addUndirectedEdge(i, dest, 1.0);
    }

    /**
     * 获取从顶点i到顶点j的路径成本，无边则返回正无穷
     */
    public double getCost(int i, int j) {
        if (i == j) {
            return 0.0;
        }
        E targetVertex = vertices.get(j);
        // 遍历顶点i的所有邻接边，找到目标顶点的权重
        for (Edge<E> edge : adjLists.get(i)) {
            if (edge.getTarget().compareTo(targetVertex) == 0) {
                return edge.getWeight();
            }
        }
        return Double.POSITIVE_INFINITY;
    }

    /**
     * 获取从顶点i到顶点j的边权重，无边则返回0
     */
    public double getEdge(int i, int j) {
        if (i == j) {
            return 0.0;
        }
        E targetVertex = vertices.get(j);
        for (Edge<E> edge : adjLists.get(i)) {
            if (edge.getTarget().compareTo(targetVertex) == 0) {
                return edge.getWeight();
            }
        }
        return 0.0;
    }

    /**
     * 判断顶点i到顶点j是否存在边
     */
    public boolean hasEdge(int i, int j) {
        if (i == j) {
            return false; // 原逻辑中顶点到自身无边，保持一致
        }
        E targetVertex = vertices.get(j);
        for (Edge<E> edge : adjLists.get(i)) {
            if (edge.getTarget().compareTo(targetVertex) == 0) {
                return true;
            }
        }
        return false;
    }

    /**
     * 根据索引获取顶点
     */
    public E getVertex(int index) {
        return vertices.get(index);
    }

    // 内部静态类：封装边的目标顶点和权重
    private static class Edge<E> {
        private final E target;
        private final double weight;

        public Edge(E target, double weight) {
            this.target = target;
            this.weight = weight;
        }

        public E getTarget() {
            return target;
        }

        public double getWeight() {
            return weight;
        }
    }
}

关键方法说明 #

1. 无向边实现：无向边的核心是双向添加边——调用addUndirectedEdge时，会先添加从i到dest的边，再找到dest对应的索引，添加反向边，确保两个顶点互相可达。
2. getCost/hasEdge方法：通过遍历顶点i对应的邻接边列表，利用泛型的compareTo方法（因为E继承了Comparable）匹配目标顶点，找到对应边的权重或判断是否存在边。
3. 泛型兼容：保留了原代码的索引式操作，同时支持自定义顶点类型（只要实现Comparable接口），你可以通过第二个构造方法传入自己的顶点列表。

内容的提问来源于stack exchange，提问作者M.T