BFS(Breadth first search) and DFS(Depth first search) are two most common ways in graph search.

BFS searches its neighbors first, and DFS searches one branch all the way and then comback.

We use BFS to find the shortest path between two nodes, and we use DFS to iterate through all the nodes, because DFS is a little simpler.

The implementations are from cracking the coding interview book. DFS uses recursion and BFS uses a queue for the implementation.

implementation of DFS :

void search(Node root) {
    if (root != null) return;
    visit(root);
    root.visited = true;
    for each (Node n in root.adjacent) {
        if (n.visited == false) {
            search(n);
        }
    }

}

and implementation of BFS is


void search(Node root) {
    Queue queue = new Queue();
    root.marked = true;
    queue.enqueue(root);

    while (!queue.isEmpty()) {
        Node r = queue.dequeue();
        visit(r);
        foreach(Node n in r.adjacent) {
            if (n.marked == false) {
                if (n.marked == false) {
                    n.marked = true;
                    queue.enqueue(n);
                }
            }
        }
    }

}