Depth-First Search (DFS)
Depth-First Search (DFS)
Depth-First Search (DFS) is a fundamental graph traversal algorithm, as its name suggests, DFS explores a graph by going as deep as possible along a path before backtracking.
Unlike BFS, which explores vertices level by level, DFS follows one path deeply and only returns to an earlier vertex when there are no more unexplored edges to follow.
1. Basic Idea of DFS
Suppose we start at vertex A:
A / \ B C / \ D E
DFS may explore the graph in the following order:
A → B → D ↑ backtrack ↓ E ↑ backtrack ↓ C
The important principle is:
Whenever possible, DFS continues to an undiscovered neighboring vertex. When there are no more undiscovered neighbors, DFS backtracks to the previous vertex.
Thus, DFS naturally uses a last-in, first-out (LIFO) strategy. The recursive implementation uses the call stack to perform this backtracking.
2. DFS Can Have Multiple Sources
This is an important difference between BFS and DFS.
In BFS, we normally start from one specified source vertex and explore all vertices reachable from it.
DFS, however, continues until every vertex in the graph has been discovered.
Suppose the graph has two disconnected components:
Component 1 Component 2 A E / \ / \ B C F G
If DFS starts at A:
A → B → C
it cannot reach E, F, or G.
Therefore, after finishing the first component, the outer DFS loop finds another WHITE vertex, say E, and starts another DFS:
A → B → C E → F → G
Thus DFS can produce a DFS forest consisting of several DFS trees.
3. DFS Colors
DFS uses three colors to represent the state of each vertex.
WHITE — Undiscovered
Initially, every vertex is WHITE.
WHITE
means:
DFS has not discovered this vertex yet.
GRAY — Discovered but Not Finished
When DFS first discovers a vertex:
WHITE → GRAY
The vertex is now being actively explored.
Its adjacency list may still contain unexplored edges.
BLACK — Finished
After DFS has examined all edges leaving the vertex:
GRAY → BLACK
The vertex is now finished.
Thus:
WHITE → GRAY → BLACK
represents the progress of a vertex during DFS.
4. DFS Uses Predecessor/Parent Information
Just as in BFS, DFS maintains a predecessor attribute:
v.π
When DFS discovers a WHITE vertex v while examining vertex u, it sets:
v.π = u
This means:
u is the parent of v in the DFS tree.
For example:
A | B / \ D E
The parent relationships are:
B.π = A D.π = B E.π = B
The edges corresponding to these parent relationships are called tree edges.
5. DFS Forest
The predecessor edges created by DFS form a DFS forest.
Why a forest rather than simply a tree?
Because the graph may be disconnected.
For example:
Tree 1 Tree 2 A E / \ / \ B C F G
The DFS forest is:
A E / \ / \ B C F G
There are two separate DFS trees.
Therefore:
DFS forest = collection of DFS treesIf the graph is connected, the DFS forest contains only one tree.
6. Discovery and Finishing Times
One of the most important features of DFS is that it assigns two timestamps to every vertex.
They are:
v.d
and
v.f
where:
- v.d = discovery time
- v.f = finishing time
Discovery Time
When DFS first discovers vertex u:
time = time + 1 u.d = time
At this point:
u: color = GRAY
The discovery time tells us when DFS first entered the vertex.
Finishing Time
After DFS has completely examined all neighbors of u:
time = time + 1 u.f = time
and:
u.color = BLACK
The finishing time tells us when DFS has completely finished processing the vertex.
Therefore:
u.d<u.ffor every vertex u.
7. Example of Discovery and Finishing Times
Consider:
A / \ B C / D
Suppose DFS visits the vertices in the order:
A → B → D → C
The timestamps could be:
A discovered: 1 B discovered: 2 D discovered: 3 D finished: 4 B finished: 5 C discovered: 6 C finished: 7 A finished: 8
So:
| Vertex | Discovery | Finish |
|---|---|---|
| A | 1 | 8 |
| B | 2 | 5 |
| D | 3 | 4 |
| C | 6 | 7 |
Notice:
A: 1 ............... 8 B: 2 ......... 5 D: 3 ... 4 C: 6 ... 7
The timestamps provide valuable information about the structure and behavior of DFS.
8. The DFS Procedure
Main DFS
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)
The first loop initializes all vertices.
The second loop ensures that every vertex is eventually discovered, even if the graph is disconnected.
DFS-VISIT
The main recursive procedure is:
DFS-VISIT(G,u) time = time + 1 u.d = time u.color = GRAY for each vertex v in Adj[u] if v.color == WHITE v.π = u DFS-VISIT(G,v) time = time + 1 u.f = time u.color = BLACK
Let's understand this step by step.
Step 1: Discover u
When DFS-VISIT(u) begins:
time = time + 1 u.d = time u.color = GRAY
So DFS has entered vertex u.
Step 2: Examine Neighbors
DFS examines:
Adj[u]
one vertex at a time.
If it finds a WHITE vertex v:
v.color == WHITE
then:
v.π = u
and DFS recursively calls:
DFS-VISIT(v)
This is the step that makes DFS go deeper.
9. Backtracking
Suppose we have:
A → B → C
DFS discovers:
A ↓ B ↓ C
When C has no more undiscovered neighbors, DFS finishes C:
C → BLACK
and returns to B.
If B has no more undiscovered neighbors, B is finished:
B → BLACK
and DFS returns to A.
This is called backtracking.
Thus the pattern is:
Go deeper ↓ Discover a new vertex ↓ Go deeper ↓ No unexplored edge ↓ Backtrack ↓ Explore another edge
This is the defining behavior of DFS.
10. Example of DFS Traversal
12. DFS Tree vs BFS Tree
It is useful to contrast the two.
BFS
BFS explores:
source ↓ all neighbors ↓ next level ↓ next level
It produces a breadth-first tree.
DFS
DFS explores:
source ↓ one neighbor ↓ go deeper ↓ go deeper ↓ backtrack
It produces a depth-first tree.
| BFS | DFS |
|---|---|
| Explores level by level | Explores deeply |
| Uses FIFO queue | Uses recursion/stack |
| Finds shortest paths in unweighted graphs | Does not generally find shortest paths |
| Usually has one source | May create multiple trees |
| Produces BFS tree | Produces DFS forest |
| Uses distance attribute | Uses discovery/finish times |
13. Important Properties of DFS
Property 1: Every vertex is discovered exactly once
A vertex is discovered only when it is WHITE.
Once it becomes GRAY, it cannot become WHITE again.
Therefore, every vertex belongs to exactly one DFS tree.
Property 2: Every non-root vertex has one parent
When a vertex is first discovered:
v.π = u
After that, its parent does not change.
Therefore, every non-root vertex has exactly one parent.
Property 3: The DFS forest contains all vertices
Unlike BFS from a single source, DFS continues with new sources whenever undiscovered vertices remain.
Therefore:
VDFS forest=VEvery vertex belongs to exactly one DFS tree.
Property 4: Every vertex has two timestamps
For every vertex u:
u.d<u.fIt is:
WHITE before u.d GRAY from u.d to u.f BLACK after u.f
14. DFS for Directed and Undirected Graphs
DFS works on both:
- Undirected graphs
- Directed graphs
The same basic procedure is used.
However, the interpretation of the edges explored by DFS becomes particularly useful in directed graphs.
DFS is the foundation for several important graph algorithms, including:
- Topological sorting
- Strongly connected components
- Cycle detection
- Classification of edges
15. Overall Picture
The complete DFS process can be summarized as:
DFS | Discover a vertex | WHITE ↓ GRAY | Explore an edge | Is neighbor WHITE? / \ YES NO | | Set parent Continue search | Recursive DFS | No unexplored edges | BLACK | Backtrack
The central idea
Depth-First Search explores as deeply as possible from the current vertex. When it reaches a vertex with no unexplored outgoing edges, it backtracks to the previous vertex and continues the search. It records parent relationships to form a depth-first forest and assigns discovery and finishing timestamps to every vertex.
The DFS forest, parent pointers, and timestamps are particularly important because later graph algorithms build on these properties.
Comments
Post a Comment