Implementazione di BFS in Java

Question

Sono un principiante in Java e ho bisogno di aiuto.

Sto tentando di implementare l'algoritmo di Breadth First Search per risolvere un puzzle game (sbloccami un gioco su Android). Ho finito con la GUI, ma sono bloccato con l'algoritmo.

Finora sono in grado di contare le mosse disponibili di ciascun blocco, che si suppone siano i nodi figli del nodo radice. Ogni nodo (elenco collegato) ha la posizione di ciascun blocco e tutti i nodi vengono memorizzati in un Set.

Quello che mi serve ora è contrassegnare ogni nodo come visitato, quindi non entrare in un ciclo.

Apprezzerei qualsiasi tipo di aiuto e, per favore, correggimi se mi sbaglio con qualcosa.

Grazie in anticipo :)

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

Questo è un esempio di una ricerca in ampiezza in java se si dà un codice possiamo contribuire adattarlo al tuo

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 I non posso commentare il link di aaronman (non abbastanza rep) ma il campo visitato è un membro del campo pubblico nella classe Node.

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

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

Per quanto riguarda il nodo di stampa, presumo aaronman è solo di passaggio l'oggetto nodo al metodo di stampa ed è solo la visualizzazione qualsiasi dato della classe Node può detenere

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

Answer 4

Si prega di provare questo:

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


     } 
    } 

} 

Per ulteriori informazioni, visitare: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java.