Challenge: Implement Depth-First Search
In this lesson, you have to implement the depth-first search algorithm. A solution is placed in the "solution" section to help you, but we suggest you try to solve it on your own first.
We'll cover the following
Problem statement
In this exercise, you have to implement the depth-first search traversal in Java. It is a searching algorithm for the graph which traverses down each branch depth-wise and backtracks after reaching a leaf node. We will use our already-implemented graph class for this task (since we have already covered the implementation of graph).
Note: Your solution should work for both connected and unconnected graphs. For an unconnected graph, the order of the output should depend upon the indices in ascending order.
To solve this problem, all the previously implemented data structures will be available to us.
Input
The input is a graph in the form of an adjacency list
Output
The output is a string containing the vertices of the graph listed in the correct order of traversal.
Sample input
Graph:
Vertex | Edges |
---|---|
0 | 1, 2 |
1 | 3, 4 |
2 | None |
3 | None |
4 | None |
In the input column of the test cases, this graph is represented as:
|V|=5, E:[(0,1)(0,2)(1,3)(1,4)]
, where|V|
represents the number of vertices andE
represents the edges.
Sample output
"01342"
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.