Java'da BFS Uygulaması

Question

Java'da yeni başlayan biriyim ve biraz yardıma ihtiyacım var.

Bir bulmaca oyununu çözmek için Breadth First Search algoritmasını uygulamaya çalışıyorum (Android'de oyunu engelle). GUI ile işim bitti, ama algoritma ile sıkışıp kaldım. Şu ana kadar, kök düğümün çocuk düğümleri olması gereken her bloğun kullanılabilir hareketlerini sayabilirim. Her düğümün (bağlı liste) her bloğun konumu vardır ve tüm düğümler bir Küme'de depolanır.

Şimdi neye ihtiyacım var her düğümü ziyaret edildi olarak işaretlemek, böylece bir döngüye girmem.

Herhangi bir yardım için minnettar olurum ve eğer bir şeyle karıştırılırsam lütfen beni düzeltin. peşin :) içinde

Teşekkür

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

Bu Sizinkilere adapte

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 ben @ yardımcı olabilecek bazı kod verirsen java bir genişlik ilk aramanın bir örnektir aaronman bağlantısı hakkında yorum yapamadı (yeterli sayıda değil) ancak ziyaret edilen alan Node sınıfındaki bir kamu alanı üyesidir. Baskı Düğüm gelince

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

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

, ben aaronman sadece baskı yöntemine düğüm nesnesi geçiyor ve sadece Düğüm sınıf

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

Answer 4

bu deneyin tutabilir ne olursa olsun veri görüntülüyor varsayalım:

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


     } 
    } 

} 

Daha fazla bilgi için lütfen şu adresi ziyaret edin: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java.