Challenge: Implement Depth First Search
After the BFS algorithm, we 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 we have implemented in the previous sections.
Note: Your solution should work for both connected and unconnected graphs.
Input
A graph in the form of an adjacency list
Note: You can start the traversal from any vertex.
Output
A string containing the vertices of the graph listed in the correct order of traversal.
Sample Input
Graph:
Vertex | Edges |
---|---|
0 | None |
1 | 3, 2 |
2 | 5, 4 |
3 | None |
4 | None |
5 | None |
Sample Output
"0124536" or "0136254" or "1362540" or "1362540"
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.