在 Java 中实现 BFS

技术标签:

【中文标题】在 Java 中实现 BFS【英文标题】：Implementing BFS in Java 【发布时间】：2013-04-29 02:29:00 【问题描述】：

我是 Java 初学者，需要一些帮助。

我正在尝试实施广度优先搜索算法来解决益智游戏（在 android 上解锁我的游戏）。我已经完成了 GUI，但我被算法困住了。

到目前为止，我可以计算每个块的可用移动，这些块应该是根节点的子节点。每个节点（链表）都有每个块的位置，所有节点都存储在一个集合中。

我现在需要将每个节点标记为已访问，这样我就不会陷入无限循环。

我将不胜感激任何形式的帮助，如果我有任何错误，请纠正我。

提前致谢:)

【问题讨论】：

【参考方案1】：

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 中广度优先搜索的示例，如果您提供一些代码，我们可以帮助您适应您的代码

【讨论】：

如果你使用链表上的Deque接口，你可以很容易地把那个BFS修改为也是一个DFS（如果需要的话）。 docs.oracle.com/javase/7/docs/api/java/util/Deque.html printNode() 和 visited() 方法在哪里定义？如何模拟visited？【参考方案2】：

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);            

【讨论】：

【参考方案3】：

@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 只是将节点对象传递给打印方法，它只是显示节点类可能保存的任何数据

public void print(Node node)     System.out.println(node.data);

【讨论】：

【参考方案4】：

请试试这个：

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。

【讨论】：

在al.add(index,node.left);，为什么不直接做al.add(node.left)？ index 总是指向列表的最后一个位置...

以上是关于在 Java 中实现 BFS的主要内容，如果未能解决你的问题，请参考以下文章