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 directed 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 directed graph in the form of an adjacency list and a starting 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 | 6 |
4 | None |
5 | None |
6 | None |
Sample output
"1245360" or "1362540"
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.