Triển khai BFS trong Java

Question

Tôi là người mới bắt đầu trong Java và tôi cần trợ giúp.

Tôi đang cố gắng triển khai thuật toán Tìm kiếm đầu tiên trên Breadth để giải quyết trò chơi giải đố (Bỏ chặn trò chơi trên Android). Tôi đã làm xong với GUI, nhưng tôi bị mắc kẹt với thuật toán.

Cho đến nay tôi có thể đếm các chuyển động có sẵn của mỗi khối, được cho là các nút con của nút gốc. Mỗi nút (danh sách liên kết) có vị trí của mỗi khối và tất cả các nút đang được lưu trữ trong một Tập hợp.

Điều tôi cần bây giờ là đánh dấu từng nút là đã truy cập, vì vậy tôi không tham gia vòng lặp.

Tôi sẽ đánh giá cao bất kỳ loại trợ giúp nào và vui lòng sửa tôi nếu tôi nhầm lẫn với bất kỳ điều gì.

Cảm ơn trước :)

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

Đây là một ví dụ về tìm kiếm theo chiều rộng trong java nếu bạn đưa ra một số mã chúng tôi có thể giúp điều chỉnh nó để bạn

Answer 2

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

Answer 3

@Growler tôi không thể bình luận về liên kết của aaronman (không đủ đại diện) nhưng trường đã truy cập là một thành viên trường công khai trong lớp Nút.

public class Node{ 
    public boolean visited; 
    public Object data; 
    //other fields 

     public Node(Object data){ 
      this.visited = false; 
      this.data = data; 
     } 
} 

Đối với in Node, tôi giả sử aaronman chỉ được đi qua các đối tượng nút với phương pháp in ấn và nó chỉ được hiển thị bất kỳ dữ liệu lớp Node có thể giữ

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

Answer 4

Vui lòng thử này:

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


     } 
    } 

} 

Để biết thêm thông tin, vui lòng truy cập: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java.