Challenge: Implement Depth First Search

In this lesson, you have to implement the Depth Frist Search algorithm discussed in the previous lesson. A solution is placed in the "solution" section to help you, but we would suggest you try to solve it on your own first.

Problem Statement

In this exercise, you have to implement 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 are going to use our already-implemented class of Graph 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 output should depend upon indices in ascending order.

To solve this problem, all the previously implemented data structures will be available to us.

Input

A graph in the form of an adjacency list

Output

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 Test cases, this graph will be represented as: |V|=5, E:[(0,1)(0,2)(1,3)(1,4)], where, |V| represents the number of vertices while E represents the edges.

Valid Outputs

"01342"

and

"02143" 

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.