1

グラフ データの隣接リスト表現を使用した幅優先探索アルゴリズムのデバッグの途中ですHashMap<String, ArrayList<Edge>>。各 String キーは地下鉄駅の名前であり、各 ArrayList はその駅のエッジのリストです。

キューを使用して、グラフのノードをトラバース順に格納しています。そのため、キューの次の子の名前を調べます。次に、次のようなものを使用して、 adjacencyList からエッジの子の ArrayList を取得したいchildEdges = stationsAdjacencyList.get(childNodeName);と思います。

私の構文は少し異なりますが、以下のコードを確認してください。

現時点では、.get() 関数は ArrayList を返していませんが、null代わりに毎回返しています。HashMap ルックアップが正しいキーを受け取っていることはわかっています。関連するバケットから値を提供することを拒否しているだけです。

    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);うまくいけば、誰かが何もフェッチしない理由を教えてくれます。

ありがとう！！

4

1 に答える 1

2

したがって、適切なテストはadjacencyList.get("valid endpoint");、ハードコーディングされた値を使用して同じ場所で呼び出すと、null 以外のリストが返されるかどうかを確認することです。そうでない場合adjacencyListは、どこかで破壊さendpointNameれています。そうである場合は、あなたが思っているほど正しくありません。

于 2011-01-11T04:45:15.103 に答える