Implementing BFS in Java

Question

I am a beginner in Java, and I need some help.

I am trying to implement Breadth First Search algorithm to solve a puzzle game (Unblock Me a game on Android). I am done with the GUI, but I am stuck with the algorithm.

So far I can count the available moves of each block, which supposed to be the children nodes of the root node. Each node (linkedlist) has the position of each block, and all the nodes are being stored in a Set.

What I need now is to mark each node as visited, so I don't get into an infinite loop.

I would appreciate any kind of help, and please correct me if I am mistaken with anything.

Thanks in advance :)

Monosepalous

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

This is an example of a breadth first search in java if you give some code we can help adapt it to yours

Zamir

If you use the Deque interface on the linked list, you can easily modify that BFS to be also a DFS (if needed). docs.oracle.com/javase/7/docs/api/java/util/Deque.html – Sadonia

where are the methods printNode() and visited() defined? How can I emulate visited? – Cathexis

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

Pons

Answer 3

Please try this:

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


        }
    }

}

For more information, please visit: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java.

Hottempered

in al.add(index,node.left);, why not just doing al.add(node.left)? index is always pointing to the last place of the list... – Wicks

Answer 4

@ Growler I could not comment on aaronman's link (not enough rep) but the visited field is a public field member in the Node class.

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

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

As for print Node, I assume aaronman is just passing the node object to the print method and it is just displaying whatever data the Node class may hold

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

Mechanism