Solution: Implement Depth-First Search
Let’s solve the Implement Depth-First Search problem.
We'll cover the following
Statement
Given a directed graph represented by an adjacency array graph
and an integer source
, representing the start vertex of the graph, return an array of integers, result
that shows the order of depth-first traversal starting from the specified source
vertex.
Constraints
graph.length
graph[i][j]
Solution
To find the depth-first traversal of a given directed graph, we utilize the depth-first search (DFS) method, starting from the specified source
vertex. Explore the graph by traversing each branch as deeply as possible before backtracking. Begin from the source
vertex, and delve deeply into the graph structure by visiting adjacent vertices until we reach a leaf node or a dead-end. Unlike tree traversal, graph traversal must account for the possibility of cycles. To manage this, we maintain a record of visited vertices to avoid revisiting them. The process continues until all vertices have been explored, at which point the traversal order is returned.
Now, let’s look at the algorithm for this approach:
Initialize an empty array
result
to store the traversal order.Determine the total number of vertices in the graph and create a boolean array
visited
to keep track of visited vertices. Initialize all entries in thevisited
array as FALSE.Create an empty stack
stack
to keep track of the nodes.Push the source vertex onto the stack and mark it as visited by setting the corresponding entry in the
visited
array to TRUE.Repeat the following steps until the
stack
is not empty:Pop the top vertex from the stack and store it in
currentVertex
.Add
currentVertex
to theresult
array.Iterate through all neighbors of
currentVertex
:If a neighbor has not been visited, push it onto the stack and mark it as visited by setting the corresponding entry in the
visited
array to TRUE.
Return the
result
array containing the DFS traversal order.
Let’s have a look at the following illustrations for a better understanding of the algorithm above:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.