用Java实现BFS
我是Java的初学者，我需要一些帮助。
我正在尝试实现广度优先搜索算法来解决益智游戏（在Android上解锁我的游戏）。 我完成了GUI，但我坚持使用算法。
到目前为止，我可以计算每个块的可用移动，这些移动应该是根节点的子节点。 每个节点（linkedlist）具有每个块的位置，并且所有节点都存储在Set中。
我现在需要的是将每个节点标记为已访问，因此我不会进入循环。
我会感激任何帮助，如果我误解了任何事情，请纠正我。
提前致谢 ：）
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(); } 这是一个在Java中进行广度优先搜索的示例，如果您提供一些代码，我们可以帮助它适应您的
public static void bfs(BinaryTree.Node root) { BinaryTree.Node temp; //a binary tree with a inner generic node class Queue> 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); } } }
@ Growler我无法评论aaronman的链接（没有足够的代表），但是被访问的字段是Node类中的公共字段成员。
public class Node{ public boolean visited; public Object data; //other fields public Node(Object data){ this.visited = false; this.data = data; } }
至于打印节点，我假设aaronman只是将节点对象传递给print方法，它只是显示Node类可以容纳的任何数据
public void print(Node node){ System.out.println(node.data); }
请试试这个：
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 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); } } }
有关更多信息，请访问： https ： //github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java 。