Challenge 2: Implement Depth First Search

After the BFS algorithm, you will now tackle the implementation for "Depth First Search".

Problem statement

You have to implement the Depth First Search algorithm on a graph using the data structures, which were implemented in the previous sections.

Note: Your solution should work for both connected and unconnected graphs.

Input

The input is a graph in the form of an adjacency list

Note: You can start the traversal from any vertex.

Output

The output is a string containing the vertices of the graph listed in the correct order of traversal.

Sample input

Graph:

Vertex Edges
1 3, 2
2 5, 4
3 6
4 None
5 None

Sample output

"124536" or "136254" or "136254" or "136254"

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