Pacific-Design.com

    
Home Index

1. Binary Search Tree

2. 1 Breadth First Search

Binary Search Tree / 1 Breadth First Search /

Graph Traversal - Breadth First Search

Searching a node and its siblings before going on to any children.

public class BreadthFirstSearch {

    public void search(Node root) {

        Queue queue = new Queue();                  // create a queue
        visit(root);                                // get root children
        root.visited = true;
        queue.enqueue(root);                        // add node to the queue

        while(!queue.isEmpty()) {

            Node parent = queue.dequeue();          // remove node from the queue

            foreach(Node node in parent.adjacent) { // iterate through each adjacent parent node

                if(node.visited == false) {         // visit node if was not visited
                    visit(node);
                    node.visited = true;
                    queue.enqueue(node);            // remove node from the queue
                }
            }
        }
    }
}

Graph Searches in Java

http://algs4.cs.princeton.edu/40graphs/