java - 如何使用集合和队列查找图的可达性

Question

我在查找可从给定节点访问的所有节点时遇到一些问题。除非使用 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.

Answer 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);
        }
    }
}