There are two methods for searching graphs that are extremely prevalent, and will form the foundations for more advanced algorithms later on. These two methods are the Depth First Search and the Breadth First Search.

**Depth First Search **

The depth first search method, which will utilize a stack. This stack can either by represented explicitly (by a stack data-type in our language) or implicitly when using recursive functions.

**Stack** is one of the simplest data structures available. There are four main operations on a stack:

Push – Adds an element to the top of the stack

Pop – Removes the top element from the stack

Top – Returns the top element on the stack

Empty – Tests if the stack is empty or not

In Java, we use the Stack class:

import java.util.*;

Stack stack = new Stack();

The depth first search is well geared towards problems where we want to find any solution to the problem (not necessarily the shortest path), or to visit all of the nodes in the graph.

the memory for the implicit stack, is more limited than the general heap memory.

Stack memory is used whenever you call a function; the variables to the function are pushed onto the stack by the compiler for you. When using a recursive function, the variables keep getting pushed on until the function returns. Also any variables the compiler needs to save between function calls must be pushed onto the stack as well. This makes it somewhat difficult to predict if you will run into stack difficulties. I recommend using the explicit Depth First search for every situation you are at least somewhat concerned about recursion depth.

**Basic Structure of DFS**

void dfs(node start) {

stack s;

s.push(start);

while (s.empty() == false) {

top = s.top();

s.pop();

mark top as visited;

check for termination condition

add all of top’s unvisited neighbors to the stack.

mark top as not visited;

}

}

**Queue **is a simple extension of the stack data type. Whereas the stack is a FILO (first-in last-out) data structure the queue is a FIFO (first-in first-out) data structure.

There are four main operations on a queue:

- Push – Adds an element to the back of the queue
- Pop – Removes the front element from the queue
- Front – Returns the front element on the queue
- Empty – Tests if the queue is empty or not

In Java, we unfortunately don’t have a Queue class, so we will approximate it with the LinkedList class.The operations map to the LinkedList class as follows:

- Push – boolean LinkedList.add(Object o)
- Pop – Object LinkedList.removeFirst()
- Front – Object LinkedList.getFirst()
- Empty – int LinkedList.size()

**Breadth First Search**

The Breadth First search is an extremely useful searching technique. It differs from the depth-first search in that it uses a queue to perform the search, so the order in which the nodes are visited is quite different. It has the extremely useful property that if all of the edges in a graph are unweighted (or the same weight) then the first time a node is visited is the shortest path to that node from the source node.

void bfs(node start) {

queue s;

s.push(start);

while (s.empty() == false) {

top = s.front();

s.pop();

mark top as visited;

check for termination condition (have we reached the node we want to?)

add all of top’s unvisited neighbors to the stack.

}

}

DFS and BFS differ only in the data structure used and BFS doesn’t mark top as unvisited again.