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

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