如何使用广度优先搜索输出最短路径而不仅仅告诉我是否存在一条路径？

Question

我正在尝试创建一个程序，可以添加节点并使用LinkedList将它们连接起来。一旦这些节点被连接起来，我想使用Breadth First Search找到它们之间的最短路径。目前我的程序只能找到是否有路径，但我想知道这条路径是什么。我该如何修改代码？

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

- Edward Cunningham

---

@CharlesLanglois 他的代码只使用了 LinkedList 而非 Queue 来进行 BFS。Linkedlist.remove() 将移除链表头部。 - XPLOT1ON

Answer 1

欢迎来到Stackoverflow.com，虽然这听起来像是一道作业题，但我会尝试引导您找到解决方案，而不是直接给出编码解决方案。

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

对于最短路径，我通常做的是对于每个已访问的节点，我保留了我来自哪个节点的先前节点。一旦我到达目的地，我将回溯我来的路径，并将该路径反转以使其正确定向。

- XPLOT1ON

---

在图中，保留前一个节点并不能帮助回溯到起始节点。你需要在路径上跟踪所有前置节点。 - Charles Langlois

@CharlesLanglois 是的，那就是我想表达的意思，如果我没有表达清楚，请原谅。 - XPLOT1ON

Answer 2

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

与其仅在队列中保留下一个要访问的节点，不如保留（单向）链表，其头部是未访问的节点，尾部包含从起始节点构建路径的已访问节点。搜索循环将从队列中弹出路径，查看头部，将其添加到已访问节点集合中（如果尚未在其中），然后从每个邻居创建新路径（链接列表）并将其添加到队列中。算法成功时，而不是返回“True”，它将返回当前路径，或者在搜索失败时返回“Null”。

然而，如果你正在使用Java（从代码中推断），使用“LinkedList”数据结构（双向链表）意味着构建新路径（在访问新节点后分支）将需要复制整个列表并将当前节点的子项添加到该新列表，并将其添加到队列中。这会浪费大量空间和时间。不幸的是，Java似乎没有包含单链表实现，这将允许共享列表的尾部（有效地创建一棵树，每个指向队列的指针都指向该树的叶子），并且更节省内存和时间。

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

对于后一种解决方案，请查看functionaljava（list interface）或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;
    }

请注意，如果您只想知道路径（即打印该路径上节点的名称），而不是实际引用该路径，请在返回之前遍历列表并打印每个节点：

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

- Charles Langlois

Answer 3

只需在将节点推入哈希集时立即打印已访问的节点。路径将被打印出来。

之后 **

visited.add(node)

打印节点的值

- Shaun_stark007.