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
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.