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

3 回答

• 0

  广度优先将探索所有路径上的所有节点，直到到达目的地 . 在找到合适的路径之前，您需要跟踪您正在访问的所有路径 .

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

  但是，如果您使用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;
      }
  

  回复于 2024-05-15T22:27:00+08:00
• 0

  只要在哈希集中按下它就打印受访节点 . 路径将被打印出来..

  **之后

  visited.add（节点）

  **打印节点的值

  回复于 2024-05-15T22:27:00+08:00
• 0

  欢迎来到Stackoverflow.com，虽然这听起来像是一个家庭作业问题，但我会尽力指导您完成解决方案而不是为您提供编码解决方案 .

  如果您有连接图，BFS通过遍历最近的未访问节点来工作，此功能允许您到达最近的某些节点 .

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

  回复于 2024-05-15T22:27:00+08:00