如何修改给定Java代码实现无向加权图的邻接表？

我来帮你把这段代码改成能实现无向加权图的邻接表结构，先梳理下原代码的问题：它的邻接节点只记录了节点索引，没有权重信息，也没处理无向图需要双向添加边的逻辑，还有一些关键方法不完整。下面是修改后的完整代码，我会同步说明改动细节：

改动说明 #

• 给AdjacentNode新增权重字段，同时把原parentNodeIndex改名为targetNodeIndex（命名更贴合实际：表示当前顶点指向的目标邻接节点），调整构造方法传入权重。
• 完善Graph类的初始化逻辑，确保每个顶点位置都被初始化。
• 新增核心操作方法：添加顶点、添加无向加权边、根据名称查找顶点索引、打印图结构。

修改后的完整代码 #

import java.util.*;

class Graph {
    private int numVertices;
    private Vertex[] adjLists;

    // 邻接节点类：记录目标节点索引和边的权重
    class AdjacentNode {
        public int targetNodeIndex;
        public int weight;
        public AdjacentNode next;

        public AdjacentNode(int targetIndex, int edgeWeight, AdjacentNode nextNode) {
            this.targetNodeIndex = targetIndex;
            this.weight = edgeWeight;
            this.next = nextNode;
        }
    }

    // 顶点类：保存顶点名称和邻接节点链表
    class Vertex {
        String name;
        AdjacentNode neighborList;

        public Vertex(String name) {
            this.name = name;
            this.neighborList = null; // 初始化邻接列表为空
        }

        @Override
        public String toString() {
            return "(" + name + ")";
        }
    }

    // 图的构造方法：初始化顶点数组
    public Graph(int n) {
        numVertices = 0;
        adjLists = new Vertex[n];
        // 初始化每个顶点位置，避免后续添加时空指针
        for (int i = 0; i < n; i++) {
            adjLists[i] = new Vertex("");
        }
    }

    // 添加顶点：给顶点数组的指定位置设置名称
    public void addVertex(String name) {
        if (numVertices < adjLists.length) {
            adjLists[numVertices].name = name;
            numVertices++;
        } else {
            System.out.println("图的顶点数量已达上限！");
        }
    }

    // 根据顶点名称查找对应的索引
    private int getVertexIndex(String name) {
        for (int i = 0; i < numVertices; i++) {
            if (adjLists[i].name.equals(name)) {
                return i;
            }
        }
        return -1; // 没找到返回-1
    }

    // 添加无向加权边：双向添加邻接节点
    public void addEdge(String sourceName, String targetName, int weight) {
        int sourceIndex = getVertexIndex(sourceName);
        int targetIndex = getVertexIndex(targetName);

        if (sourceIndex == -1 || targetIndex == -1) {
            System.out.println("指定的顶点不存在！");
            return;
        }

        // 向源顶点的邻接列表添加目标节点（带权重）
        adjLists[sourceIndex].neighborList = new AdjacentNode(targetIndex, weight, adjLists[sourceIndex].neighborList);
        // 无向图需要反向添加：向目标顶点的邻接列表添加源节点（带权重）
        adjLists[targetIndex].neighborList = new AdjacentNode(sourceIndex, weight, adjLists[targetIndex].neighborList);
    }

    // 打印图的邻接表结构
    public void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            Vertex currentVertex = adjLists[i];
            System.out.print("顶点 " + currentVertex.name + " 的邻接节点：");
            AdjacentNode currentNode = currentVertex.neighborList;
            while (currentNode != null) {
                Vertex neighborVertex = adjLists[currentNode.targetNodeIndex];
                System.out.print(neighborVertex.name + "(权重:" + currentNode.weight + ") ");
                currentNode = currentNode.next;
            }
            System.out.println();
        }
    }

    // 测试示例
    public static void main(String[] args) {
        Graph weightedUndirectedGraph = new Graph(5);
        // 添加顶点
        weightedUndirectedGraph.addVertex("A");
        weightedUndirectedGraph.addVertex("B");
        weightedUndirectedGraph.addVertex("C");
        weightedUndirectedGraph.addVertex("D");
        weightedUndirectedGraph.addVertex("E");
        // 添加无向加权边
        weightedUndirectedGraph.addEdge("A", "B", 2);
        weightedUndirectedGraph.addEdge("A", "C", 5);
        weightedUndirectedGraph.addEdge("B", "D", 3);
        weightedUndirectedGraph.addEdge("C", "D", 1);
        weightedUndirectedGraph.addEdge("D", "E", 4);
        // 打印图结构
        weightedUndirectedGraph.printGraph();
    }
}

代码说明 #

• AdjacentNode：现在不仅记录目标节点的索引，还保存了边的权重，完全符合加权图的需求。
• addEdge方法：因为是无向图，所以添加边时需要在两个顶点的邻接列表中都添加对方的节点，保证双向的邻接关系。
• 测试示例：创建了一个5个顶点的无向加权图，添加了若干带权重的边，运行后会清晰打印每个顶点的邻接节点及对应的权重。

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