xkcd/761

**Depth-First Search**

One thing that is important to understand is that the Breadth-First Search algorithm generates a tree as it searches a graph (for a proof of this, refer to Lemma 22.6 in Chapter 22 of *Introduction to Algorithms *3rd Edition by Cormen et al.). This is called a Breadth-First Tree. A **Depth-First **Search, on the other hand, does not generate a single tree. Instead, it generates several trees (called depth-first trees) and creates a depth-first forest.

Check this animation out to get a general understand of how a depth-first search works.

Here is the pseudocode for the Depth-First Search algorithm:

DFS(G)
for each vertex u ϵ G.V
u.color = WHITE
u.π = NIL
time = 0
for each vertex u ϵ G.V
if u.color = WHITE
DFS-VISIT(G, u)
DFS-VISIT(G, u)
time = time + 1 // white vertex discovered
u.d = time
u.color = GRAY
for each v ϵ G.Adj[u] // explore edge (u, v)
if v.color == WHITE
v.π = u
DFS-VISIT(G, v)
u.color = BLACK // u is finished. Mark it black.
time = time + 1
u.f = time

**Notation**

Most of the notation is very similar to that used in the Breadth-First Search pseudocode with one key difference. Let be a vertex in . The property does *not* store the distance from the source, unlike in BFS. Instead it, along with the new property store **time-stamps**.

- stores the time when the vertex is discovered by the algorithm
- stores the time when the algorithm finishes scanning the adjacency list of and sets its color to black.
- The global variable is used for the above described time-stamping.

The following two GIFs provide a good comparison between a BFS and a DFS.

### Like this:

Like Loading...

*Related*