如何使用广度优先搜索输出最短路径而不只是告诉我有路径？

Question

我正在尝试创建一个程序，我可以在其中添加节点并使用 LinkedList 连接它们。一旦我有了这些连接的节点，我想使用广度优先搜索找到它们之间的最短路径。目前我的程序只发现是否有路径，但我想知道那条路径是什么。我应该如何修改我的代码？

public static boolean findPath(String start, String destination){
            //find the nodes given the String key
            Node current = getNode(start);
            Node end = getNode(destination);

            //create a linked list to store the visited nodes
            LinkedList<Node> nextToVisit = new LinkedList<Node>();
            HashSet<Node> visited= new HashSet<Node>();
            nextToVisit.add(current);
            while(!nextToVisit.isEmpty()){
                Node node = nextToVisit.remove();
                System.out.println(node.name);
                if(node == end)
                    return true;
                if(visited.contains(node))
                    continue;
                visited.add(node);
                for(Node children : node.adjacent){
                    nextToVisit.add(children);
                }
            }
            return false;
        }

Answer 1

只要将访问过的节点推送到哈希集中就打印出来.. 路径将被打印..

**之后

visited.add(node)

** 打印节点

的值

Answer 2

欢迎来到 whosebug.com，虽然这听起来像是一道家庭作业题，但我会尽量引导您完成解决方案，而不是给您编码解决方案。

如果你有一个连通图，BFS 通过遍历最近的未访问节点来工作，这个特性允许你到达最近的某个节点。

对于最短路径，我通常做的是对于每个访问过的节点，我保留我来自的前一个节点。到达目的地后，我会原路返回，然后倒转该路径以将其置于正确的方向。

Answer 3

广度优先将探索所有路径上的所有节点，直到到达目的地。您需要跟踪您访问的所有路径，直到找到正确的路径。

您可以保留（单）链表，其头部是未访问的节点，其尾部包含从起始节点构建路径的已访问节点，而不是只保留下一个要访问的节点。搜索循环将从队列中弹出一条路径，查看头部，将其添加到已访问节点集（如果尚未在其中），然后从每个邻居创建一个新路径（链表），并添加那些到队列。该算法不是 returning "True"，而是在成功时 return 当前路径，或者在搜索失败时 "Null"。

但是，如果您使用 Java（我从代码中推断），使用 "LinkedList" 数据结构（这是一个双向链表）将意味着构建一个新路径（访问新节点后分支）需要复制整个列表并将当前节点的子节点添加到该新列表，并将其添加到队列中。这会浪费很多 space 和时间。可悲的是，Java 似乎不包含单链表实现，这将允许共享列表的尾部（有效地创建一棵树，队列中的每个指针都指向该树的叶子）并且会内存和时间效率更高。

因此，要实施该解决方案，您需要自己实施单向链表，或者使用提供实施的库。自己实现它并不太难，因为它是一个非常简单的数据结构，并且有很多资源和示例（从 Wikipedia 开始）。

后面的解决方法，看functionaljava(list interface) or vavr(list interface).

代码如下，使用单链表的 vavr 库语法：

public static List<Node> findPath(String start, String destination){
        //find the nodes given the String key
        Node current = getNode(start);
        Node end = getNode(destination);

        //create a linked list to store the visited nodes
        LinkedList<List<Node>> nextToVisit = new LinkedList<List<Node>>();
        HashSet<Node> visited= new HashSet<Node>();
        List<Node> currentPath = List.of(current);
        nextToVisit.add(currentPath);
        while(!nextToVisit.isEmpty()){
            List<Node> path = nextToVisit.remove();
            //get the "head" of current path, which is the unvisited node
            Node node = path.peek();
            System.out.println(node.name);
            if(node == end)
                return path;//return current path
            if(visited.contains(node))//this path doesn't lead anywhere
                continue;
            visited.add(node);
            for(Node children : node.adjacent){
                nextToVisit.add(path.prepend(children));//adding new path
            }
        }
        return null;
    }

请注意，如果您只想知道路径（即打印该路径上节点的名称），而没有对该路径的实际引用，只需遍历列表并在 [= 之前打印每个节点33=]ing:

public static boolean findPath(String start, String destination){
        //find the nodes given the String key
        Node current = getNode(start);
        Node end = getNode(destination);

        //create a linked list to store the visited nodes
        LinkedList<List<Node>> nextToVisit = new LinkedList<List<Node>>();
        HashSet<Node> visited= new HashSet<Node>();
        List<Node> currentPath = List.of(current);
        nextToVisit.add(currentPath);
        while(!nextToVisit.isEmpty()){
            List<Node> path = nextToVisit.remove();
            //get the "head" of current path, which is the unvisited node
            Node node = path.peek();
            System.out.println(node.name);
            if(node == end){
                System.out.println("The path:");
                for(Node n: path)
                    System.out.println(n.name);
                return true;//return current path
            }
            if(visited.contains(node))//this path doesn't lead anywhere
                continue;
            visited.add(node);
            for(Node children : node.adjacent){
                nextToVisit.add(path.prepend(children));//adding new path
            }
        }
        return false;
    }

如何使用广度优先搜索输出最短路径而不只是告诉我有路径？

How do I use Breadth First Search to output the shortest path and not just tell me there is a path?

graph-theory

breadth-first-search