广度优先搜索 - Java
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12555501/
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
Breadth First Search - Java
提问by mrjasmin
I have as a school excersice to implement breadth first search in java. I have implemented almost everything but the problem is that my search is not working and I cant find the problem :( So Im asking you to advice me and give me some guidlines on where the eventual problem could be.
作为学校的练习，我在 Java 中实现了广度优先搜索。我已经实现了几乎所有的东西，但问题是我的搜索不起作用，我找不到问题:( 所以我请你给我建议，并给我一些关于最终问题可能在哪里的指导方针。
public ArrayList<SearchNode> search(Problem p) {
// The frontier is a queue of expanded SearchNodes not processed yet
frontier = new NodeQueue();
/// The explored set is a set of nodes that have been processed
explored = new HashSet<SearchNode>();
// The start state is given
GridPos startState = (GridPos) p.getInitialState();
// Initialize the frontier with the start state
frontier.addNodeToFront(new SearchNode(startState));
// Path will be empty until we find the goal.
path = new ArrayList<SearchNode>();
// The start NODE
SearchNode node = new SearchNode(startState);
// Check if startState = GoalState??
if(p.isGoalState(startState)){
path.add(new SearchNode(startState));
return path;
}
do {
node = frontier.removeFirst();
explored.add(node);
ArrayList reachable = new ArrayList<GridPos>();
reachable = p.getReachableStatesFrom(node.getState());
SearchNode child;
for(int i = 0; i< reachable.size(); i++){
child = new SearchNode((GridPos)reachable.get(i));
if(!(explored.contains(child) || frontier.contains(child))){
if(p.isGoalState(child.getState())){
path = child.getPathFromRoot() ;
return path;
}
frontier.addNodeToFront(child);
}
}
}while(!frontier.isEmpty());
return path;
}
Thank you
谢谢
回答by Alex Lynch
frontier.addNodeToFront(child);
assuming the rest of your code (getReachableStatesFrom(), etc) is correct, adding elements to the front of your queue will cause your code to execute as a depth first search.
假设您的其余代码（getReachableStatesFrom() 等）是正确的，将元素添加到队列的前面将导致您的代码作为深度优先搜索执行。
回答by Mohammad
For implementing the breadth first search, you should use a queue. This process may become very complicated. So, it is better to keep it simple. You should push the children of a node to the queue (left then right) and then visit the node (print data). Then, yo should remove the node from the queue. You should continue this process till the queue becomes empty. You can see my implementation of the BFS here: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java
为了实现广度优先搜索，您应该使用队列。这个过程可能会变得非常复杂。所以，最好保持简单。您应该将节点的子节点推入队列（从左到右），然后访问该节点（打印数据）。然后，你应该从队列中删除节点。您应该继续这个过程，直到队列变空。你可以在这里看到我对 BFS 的实现：https: //github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java
