# Algorithms Notes – Chapter 8

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 $v$ be a vertex in $G$. The property $v.d$ does not store the distance from the source, unlike in BFS. Instead it, along with the new property $v.f$ store time-stamps.

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

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

Advertisements