java 用广度优先搜索寻找最短路径节点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/41789767/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding the shortest path nodes with breadth first search
提问by underdog
I am running breadth first search on the above graph to find the shortest path from Node 0to Node 6.
我在上图中运行广度优先搜索以找到从Node 0到的最短路径Node 6。
My code
我的代码
public List<Integer> shortestPathBFS(int startNode, int nodeToBeFound){
boolean shortestPathFound = false;
Queue<Integer> queue = new LinkedList<Integer>();
Set<Integer> visitedNodes = new HashSet<Integer>();
List<Integer> shortestPath = new ArrayList<Integer>();
queue.add(startNode);
shortestPath.add(startNode);
while (!queue.isEmpty()) {
int nextNode = queue.peek();
shortestPathFound = (nextNode == nodeToBeFound) ? true : false;
if(shortestPathFound)break;
visitedNodes.add(nextNode);
System.out.println(queue);
Integer unvisitedNode = this.getUnvisitedNode(nextNode, visitedNodes);
if (unvisitedNode != null) {
queue.add(unvisitedNode);
visitedNodes.add(unvisitedNode);
shortestPath.add(nextNode); //Adding the previous node of the visited node
shortestPathFound = (unvisitedNode == nodeToBeFound) ? true : false;
if(shortestPathFound)break;
} else {
queue.poll();
}
}
return shortestPath;
}
I need to track down the nodes through which the BFS algo. traversed to reach node 6, like [0,3,2,5,6]. For that I have created a List named shortestPath& trying to store the previous nodes of the visited nodes, to get the list of nodes. Referred
我需要追踪 BFS 算法通过的节点。遍历到节点 6，如[0,3,2,5,6]。为此，我创建了一个名为shortestPath&的列表，试图存储已访问节点的先前节点，以获取节点列表。转介
But it doesn't seem to work. The shortest path is [0,3,2,5,6]
但它似乎不起作用。最短路径是[0,3,2,5,6]
In the list what I get is Shortest path: [0, 0, 0, 0, 1, 3, 3, 2, 5]
在列表中我得到的是 Shortest path: [0, 0, 0, 0, 1, 3, 3, 2, 5]
It's partially correct but gives the extra 1.
它部分正确，但提供了额外的1.
If I again start from the first element 0of the shortestPathlist & start traversing & backtracking. Like 1doesn't has an edge to 3, so I backtrack & move from 0to 3to 5, I will get the answer but not sure if that's the correct way.
如果我再次从第一个元素开始0的的shortestPath名单和启动遍历和回溯。就像1不具备优势来3，所以我原路返回，从与移动0至3到5，我会得到答案，但不知道这是正确的做法。
What is the ideal way to getting the nodes for the shortest path?
获取最短路径节点的理想方法是什么？
回答by Anton
Storing all the visited nodes in a single list is not helpful for finding the shortest path because in the end you have no way of knowing which nodes were the ones that led to the target node, and which ones were dead ends.
将所有访问过的节点存储在单个列表中对于找到最短路径没有帮助，因为最终您无法知道哪些节点是通向目标节点的节点，哪些是死胡同。
What you need to do is for every nodeto store the previous node in the path from the starting node.
您需要做的是为每个节点存储从起始节点开始的路径中的前一个节点。
So, create a map Map<Integer, Integer> parentNodes, and instead of this:
所以，创建一个 map Map<Integer, Integer> parentNodes，而不是这个：
shortestPath.add(nextNode);
do this:
做这个：
parentNodes.put(unvisitedNode, nextNode);
After you reach the target node, you can traverse that map to find the path back to the starting node:
到达目标节点后，您可以遍历该映射以找到返回起始节点的路径：
if(shortestPathFound) {
List<Integer> shortestPath = new ArrayList<>();
Integer node = nodeToBeFound;
while(node != null) {
shortestPath.add(node)
node = parentNodes.get(node);
}
Collections.reverse(shortestPath);
}
回答by c0der
As you can see in acheron55 answer:
正如你在acheron55 的回答中看到的：
"It has the extremely useful property that if all of the edges in a graph are unweighted (or the same weight) then the first time a node is visited is the shortest path to that node from the source node"
“它具有非常有用的特性，如果图中的所有边都未加权（或相同的权重），那么第一次访问节点时是从源节点到该节点的最短路径”
So all you have to do, is to keep track of the path through which the target has been reached.
A simple way to do it, is to push into the Queuethe whole path used to reach a node, rather than the node itself.
The benefit of doing so is that when the target has been reached the queue holds the path used to reach it.
Here is a simple implementation :
因此，您所要做的就是跟踪到达目标的路径。一个简单的方法是推入Queue用于到达节点的整个路径，而不是节点本身。
这样做的好处是，当到达目标时，队列会保留用于到达它的路径。
这是一个简单的实现：
/**
* unlike common bfs implementation queue does not hold a nodes, but rather collections
* of nodes. each collection represents the path through which a certain node has
* been reached, the node being the last element in that collection
*/
private Queue<List<Node>> queue;
//a collection of visited nodes
private Set<Node> visited;
public boolean bfs(Node node) {
if(node == null){ return false; }
queue = new LinkedList<>(); //initialize queue
visited = new HashSet<>(); //initialize visited log
//a collection to hold the path through which a node has been reached
//the node it self is the last element in that collection
List<Node> pathToNode = new ArrayList<>();
pathToNode.add(node);
queue.add(pathToNode);
while (! queue.isEmpty()) {
pathToNode = queue.poll();
//get node (last element) from queue
node = pathToNode.get(pathToNode.size()-1);
if(isSolved(node)) {
//print path
System.out.println(pathToNode);
return true;
}
//loop over neighbors
for(Node nextNode : getNeighbors(node)){
if(! isVisited(nextNode)) {
//create a new collection representing the path to nextNode
List<Node> pathToNextNode = new ArrayList<>(pathToNode);
pathToNextNode.add(nextNode);
queue.add(pathToNextNode); //add collection to the queue
}
}
}
return false;
}
private List<Node> getNeighbors(Node node) {/* TODO implement*/ return null;}
private boolean isSolved(Node node) {/* TODO implement*/ return false;}
private boolean isVisited(Node node) {
if(visited.contains(node)) { return true;}
visited.add(node);
return false;
}
This is also applicable to cyclic graphs, where a node can have more than one parent.
这也适用于循环图，其中一个节点可以有多个父节点。
回答by Tymur Gubayev
In addition to the already given answer by user3290797.
除了 user3290797 已经给出的答案。
It looks like You are dealing with an unweighted graph. We interpret this as every edge has a weight of 1. In this case, once You have associated a distance to the root node with every node of the graph (the breadth-first traversal), it becomes trivial to reconstruct the shortest path from any node, and even detect if there are multiple ones.
看起来您正在处理一个未加权的图表。我们将其解释为每条边的权重为 1。在这种情况下，一旦您将到根节点的距离与图的每个节点（广度优先遍历）相关联，从任何节点，甚至检测是否有多个节点。
All You need to do is a breadth- (in case You want every shortest path) or depth-first traversal of the same graph starting from the target node and only considering neighbours with a depth's value of exactly 1 less.
您需要做的就是从目标节点开始对同一图进行广度（如果您想要每条最短路径）或深度优先遍历，并且仅考虑深度值恰好小于 1 的邻居。
So we need to jump from distance 4 (node 6) to 3, 2, 1, 0, and there is only one way (in this case) to do so.
所以我们需要从距离 4（节点 6）跳转到 3、2、1、0，并且只有一种方法（在这种情况下）可以这样做。
In case we are interested in the shortest path to node 4 the result would be distances 2-1-0 or nodes 4-3-0 or 4-8-0.
如果我们对到节点 4 的最短路径感兴趣，结果将是距离 2-1-0 或节点 4-3-0 或 4-8-0。
BTW, this approach can easily be modified to work with weighted graphs (with non-negative weights) too: valid neighbours are those with distance equals to current minus the weight of the edge -- this involves some actual calculations and directly storing previous nodes along the shortest path might be better.
顺便说一句，这种方法也可以很容易地修改为使用加权图（具有非负权重）：有效邻居是那些距离等于当前减去边权重的邻居——这涉及一些实际计算并直接存储以前的节点最短路径可能更好。
