使用BFS的2个节点之间的路径

我已经编写了一个函数，用于计算使用BFS是否可以从源顶点到达目标顶点。现在我需要跟踪我用来达到顶点的路径。我想这应该是一个小小的调整，我们可以将节点添加到我的路径数组列表中。有人请帮助我。使用BFS的2个节点之间的路径

public Boolean isReachable(Node destination) { 
    ArrayList<Node> visited = new ArrayList<>(); 
    LinkedList<Node> queue = new LinkedList<>(); 
    ArrayList<Node> path = new ArrayList<>(); 
    queue.add(this); 

    while (queue.size() != 0) { 
     Node source = queue.poll(); 

     for (Node node : source.adjacentNodes) { 
      if (node.equals(destination)) 
       return true; 

      if (!visited.contains(node)) { 
       visited.add(node); 
       queue.add(node); 
      } 

     } 
    } 
    return false; 
}

来源

2016-03-01 Ritabrata

可能重复[只返回实际最短路径中的顶点]（http://stackoverflow.com/questions/5463505/returning-only-the-vertices-in-act-shortest-path） –

BFS缺少两个部分。 BFS用于查找节点之间的路径，但它也尝试查找最短路径（但仅查找它搜索的节点），因此通常涉及成本值。既然你只关心节点是否连接，那么你就不需要这个成本值。

缺少的第二部分是跟踪通向队列中当前节点的父节点。看到这里写的伪代码：https://en.wikipedia.org/wiki/Breadth-first_search请注意他们对n.parent和n.distance的使用。

跟踪另一个数据结构中当前节点的父引用，或者添加一个指向Node节点对象内父节点的指针。然后，一旦当前节点等于目标节点，则可以将父节点指针向后跟随到起始节点。这将为您提供从完成节点到开始节点的完整路径。

如果你想从开始到完成的路径，你需要遍历父节点并将它们的引用存储在列表或其他东西中，并在完成时反转列表。

来源

2016-03-01 20:49:16 Tansir1

所以你得到了你的bfs算法，但无法检索到实际的路径。您只需搜索相同的问题是否已被回答before。

来源

2016-03-10 16:02:01 Bazz

使用BFS的2个节点之间的路径

回答

相关问题