在Java中实现BFS

我是一名Java初学者，我需要一些帮助。在Java中实现BFS

我想实现广度优先搜索算法来解决一个益智游戏（在Android上解锁我的游戏）。我完成了GUI，但是我坚持使用算法。

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

我现在需要的是将每个节点标记为已访问，所以我不会陷入循环。

我将不胜感激任何形式的帮助，如果我误解了任何内容，请纠正我。

感谢提前:)

2013-05-04 Mahmoud Abubakr

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

这是如果你给一些代码，我们可以帮助它适应你的

来源

2013-05-04 23:54:53 aaronman

如果您在链接列表上使用'Deque'接口，则可以轻松地将该BFS修改为DFS（如果需要）。 http://docs.oracle.com/javase/7/docs/api/java/util/Deque.html – 2013-05-05 16:32:07

哪里定义了printNode（）和visited（）方法？我如何模仿'visited'？ – Growler 2013-05-29 14:24:46

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

来源

2014-09-05 08:51:45 John61590

@Growler 我在Java中的广度优先搜索的一个例子无法评论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); 
}

来源

2014-09-08 20:53:21 Joe

请试试这个：

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


     } 
    } 

}

来源

2016-08-07 00:15:31 Mohammad

在Java中实现BFS

回答

相关问题