使用 BFS 查找节点是否可达

Question

我正在使用 BFS 检查节点是否可达并打印路由。谁能解释为什么在这种情况下 BFS 比 DFS 更受欢迎？使用以下代码：

    LinkedList<String> queue = new LinkedList<String>();
    HashSet<String> visitedNodes = new LinkedHashSet<String> ();
    queue.add(source);
    visitedNodes.add(source);

    while (!queue.isEmpty()) {
        String focusNode = queue.poll();
        Set<Node> nodeSet = inputMap.getAllOutgoingNodes(focusNode);
        if (null != nodeSet) {
            for (Node s: nodeSet) {
                if (!visitedNodes.contains(s.edge1)) {
                    visitedNodes.add(s.edge1);
                    queue.add(s.edge1);
                    if (destination.equals(s.edge1)) {
                        for (String sn: visitedNodes) {
                            System.out.print(sn);     
                        break;
                    }
                }
            }
        }
    }

Answer 1

如果问题是检查节点是否可达，那么我认为 DFS 是首选（通常只是为了代码长度），如果你还必须找到一条路由，那么使用 DFS 找到的路由可能非常好很长（而且对于人类来说很难检查），因此 BFS 是首选。

但总之没有统一的规则，全看个人喜好了。

使用 BFS 查找节点是否可达

Find if a node is reachable using BFS

graph-theory

breadth-first-search