java - 邻接列表 HashMap> 无法找到其值

Question

我正在使用图形数据的邻接列表表示来调试广度优先搜索算法:HashMap<String, ArrayList<Edge>> 。每个 String 键都是一个地铁站的名称，每个 ArrayList 是该站的边列表。

我正在使用队列按照遍历的顺序存储图形的节点。所以我检查队列中的下一个是否是 child 的名字。然后我想要通过使用类似 childEdges = stationsAdjacencyList.get(childNodeName); 的东西从 adjacencyList 获取 child 的边缘 ArrayList 。

我的语法有点不同，但请检查下面的代码。

目前 .get() 函数没有返回 ArrayList，而是返回 null每次都改为。我知道 HashMap 查找正在接收正确的 key 。它只是拒绝从其关联的存储桶中向我提供任何值(value)。

    while (!q.empty()) {    // 

        String endpointName; // the Key part for the next node lookup 

        // get next node (single entry of adjacency list)
        Map<String, ArrayList<Edge>> currentNode = (Map<String, ArrayList<Edge>>) q.deque(); 

        HashMap<String, ArrayList<Edge>> nextNode = new HashMap<String, ArrayList<Edge>>();

        for (Map.Entry<String, ArrayList<Edge>> node : currentNode.entrySet()) { // there is only one node

            ++levelCount; // next node iteration is one level down the tree

            for (Edge edge : node.getValue()) {  // for each of this nodes Edges

                endpointName = edge.getEndpoint(); // retrieve the name of adjacent

                if (!endpointName.equals(destination)) { // if it's not the destination



                    levelTracker.put(edge.getParent(), levelCount); // record the level in the tree of this node

                    ArrayList<Edge> nextNodeEdges = adjacencyList.get(endpointName);

                    nextNode.put(endpointName, nextNodeEdges); // create child node from endpoint

                    q.enqueue(nextNode); // add child to queue

                }
                else if (endpointName.equals(destination)) { // if we're done

                    path.add(endpointName); // record the destination in the path (reverse order)

                    getPathBack(edge, levelCount + 1); // + 1 levelCount to indicate destination level in tree 

                    break;
                }
            }
        }

    }

如果代码不那么干净或没有像样的注释，我们深表歉意，它会不断变化。希望有人能告诉我为什么ArrayList<Edge> nextNodeEdges = adjacencyList.get(endpointName);没有获取任何内容。

谢谢!!

Answer 1

因此，一个好的测试是查看在同一位置使用硬编码值调用 adjacencyList.get("valid endpoint"); 是否会返回非空列表。如果没有，那么 adjacencyList 就会在某个地方被破坏，如果是，那么 endpointName 并不像您想象的那么正确。