0

特定のノードからアクセス可能なすべてのノードを見つけるのに苦労しています。DFS や BFS を使用せずに、セットとキューを使用して、到達可能なすべてのノードを生成しようとしています。私が理解していることから、キューを開始ノードに初期化し、開始ノードをセットに追加してキューから削除できます。セットに正常に追加された場合 (重複していない場合)、その到達可能なノードをキューに戻します。キューが空になるまでこれを繰り返し、セットを返します。

public static Set<String> reachable (Map<String, Set<String>> graph, String startNode) {
         //Set of nodes accessible from the startNode
         Set<String> reachableNodes = new ArraySet<String>();

         //Queue of accessible nodes from a given node to search from.
         Queue<String> searchNodes = new ArrayQueue<String>(graph.get(startNode));

         //Stuck here.

         return reachableNodes;
}

私は実装に少し行き詰まりました。私が試したのは、キューを反復するイテレータを宣言することです。キューに別の要素がある間に、その要素をセットに追加し、その要素をキューから削除します。しかし、セットに配置されたばかりのその要素からアクセス可能なすべてのノードをキューに戻す方法についてはわかりません。

アルゴリズム (BFS に類似):

  1. ノードにアクセスします。
  2. このノードからアクセス可能なすべてのノードをキューに追加します。
  3. キューから 1 つのノードをアクセス可能なノードのセットに最初から追加します。
  4. キューからノードを削除します。
  5. キューからセットに追加されたばかりのノードからアクセス可能なすべてのノードを、キューに戻します。
  6. キューが空になるまで繰り返します。

サンプル：

{ c : [f,e] ,
  f : [g,d] ,
  e : [d]   ,
  d : [g]   }

"Enter startNode: c"
add f,e -> queue
remove f from queue
add f to set
add g d to queue
remove e
add e to set 
add d to queue   
loop until queue is empty.
4

1 に答える 1

1

Generally speaking, the algorithm you're describing is BFS. You can do this using a while loop in your "Stuck" section:

while (searchNodes.peek() != null) {
    String next = searchNodes.remove();
    boolean isNewNode = reachableNodes.add(next);
    if (isNewNode && graph.containsKey(next)) {
        for (String node : graph.get(next)) {
            searchNodes.add(node);
        }
    }
}
于 2012-10-05T09:30:45.697 に答える