Challenge 2: Implement Depth First Search
After the BFS algorithm, you will now tackle the implementation for "Depth First Search".
We'll cover the following
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.