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

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

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

您可以保留(单)链表，其头部是未访问的节点，尾部包含从起始节点构建路径的已访问节点，而不是只保留下一个要访问的节点。搜索循环将从队列中弹出一条路径，查看头部，将其添加到已访问节点集(如果尚未在其中)，然后从每个邻居创建一个新路径(链表)，并添加那些到队列。该算法不会返回“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;
    }