Algorithms Notes – Chapter 8

dfs

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.

dfs

bfs

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s