用 Java 实现 BFS
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16380026/
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
Implementing BFS in Java
提问by Mabu
I am a beginner in Java, and I need some help.
我是 Java 的初学者，我需要一些帮助。
I am trying to implement Breadth First Search algorithm to solve a puzzle game (Unblock Me a game on Android). I am done with the GUI, but I am stuck with the algorithm.
我正在尝试实施广度优先搜索算法来解决益智游戏（在 Android 上解锁我的游戏）。我已经完成了 GUI，但我仍然坚持使用算法。
So far I can count the available moves of each block, which supposed to be the children nodes of the root node. Each node (linkedlist) has the position of each block, and all the nodes are being stored in a Set.
到目前为止，我可以计算每个块的可用移动，这些块应该是根节点的子节点。每个节点（链表）都有每个区块的位置，所有节点都存储在一个Set中。
What I need now is to mark each node as visited, so I don't get into an infinite loop.
我现在需要的是将每个节点标记为已访问，这样我就不会陷入无限循环。
I would appreciate any kind of help, and please correct me if I am mistaken with anything.
我将不胜感激，如果我有任何错误，请纠正我。
Thanks in advance :)
提前致谢 ：）
回答by aaronman
public void bfs()
{
// BFS uses Queue data structure
Queue queue = new LinkedList();
queue.add(this.rootNode);
printNode(this.rootNode);
rootNode.visited = true;
while(!queue.isEmpty()) {
Node node = (Node)queue.remove();
Node child=null;
while((child=getUnvisitedChildNode(node))!=null) {
child.visited=true;
printNode(child);
queue.add(child);
}
}
// Clear visited property of nodes
clearNodes();
}
This is an example of a breadth first search in java if you give some code we can help adapt it to yours
这是一个广度优先搜索的例子，如果你提供一些代码，我们可以帮助它适应你的
回答by John61590
public static void bfs(BinaryTree.Node<Integer> root)
{
BinaryTree.Node<Integer> temp; //a binary tree with a inner generic node class
Queue<BinaryTree.Node<Integer>> queue = new LinkedList<>(); //can't instantiate a Queue since abstract, so use LLQueue
if (root == null)
{
return;
}
queue.add(root);
while (!queue.isEmpty())
{
temp = queue.poll(); //remove the node from the queue
//process current node
System.out.println(temp.data);
//process the left child first
if (temp.left != null)
{
queue.add(temp.left);
}
//process the right child after the left if not null
if (temp.right != null)
{
queue.add(temp.right);
}
}
}
回答by Joe
@ GrowlerI could not comment on aaronman's link (not enough rep) but the visited field is a public field member in the Node class.
@ Growler我无法评论 aaronman 的链接（没有足够的代表），但访问的字段是 Node 类中的公共字段成员。
public class Node{
public boolean visited;
public Object data;
//other fields
public Node(Object data){
this.visited = false;
this.data = data;
}
}
As for print Node, I assume aaronman is just passing the node object to the print method and it is just displaying whatever data the Node class may hold
至于打印节点，我假设 aaronman 只是将节点对象传递给打印方法，它只是显示节点类可能持有的任何数据
public void print(Node node){
System.out.println(node.data);
}
回答by Mohammad
Please try this:
请试试这个：
import java.util.ArrayList;
import java.util.List;
public class TreeTraverse {
static class Node{
Node(int data){
this.data = data;
this.left = null;
this.right = null;
this.visited = false;
}
int data;
Node left;
Node right;
boolean visited;
}
public static void main(String[] args) {
//The tree:
// 1
// / \
// 7 9
// \ / \
// 8 2 3
Node node1 = new Node(1);
Node node7 = new Node(7);
Node node9 = new Node(9);
Node node8 = new Node(8);
Node node2 = new Node(2);
Node node3 = new Node(3);
node1.left = node7;
node1.right = node9;
node7.right = node8;
node9.right = node3;
node9.left = node2;
System.out.println("BFS: ");
breadthFirstSearch(node1);
}
private static void breadthFirstSearch(Node node){
List<Node> al = new ArrayList<>();
al.add(node);
while(!al.isEmpty()){
node = al.get(0);
if(node.left != null){
int index = al.size();
al.add(index,node.left);
}
if(node.right != null){
int index = al.size();
al.add(index,node.right);
}
System.out.print(al.get(0).data+" ");
al.remove(0);
}
}
}
For more information, please visit: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java.
更多信息请访问：https: //github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java。
