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. 从一开始就将队列中的一个节点添加到一组可访问节点中。
  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

一般来说，您描述的算法是BFS。您可以在“Stuck”部分中使用 while 循环来执行此操作：

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 回答