Depth-first Search (DFS) Interview Questions | Practice Problems


A Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.


Below graph shows order in which the nodes are discovered in DFS –


Below is the list of commonly asked interview questions that can be solved using DFS –


  1. Depth First Search (DFS) | Iterative & Recursive Implementation
  2. Determine if a given graph is Bipartite Graph using DFS
  3. Topological Sorting in a DAG
  4. Transitive Closure of a Graph
  5. Check if an undirected graph contains cycle or not
  6. Determine if an undirected graph is a Tree (Acyclic Connected Graph)
  7. 2-Edge Connectivity in the graph
  8. Check if given digraph is a DAG (Directed Acyclic Graph) or not
  9. Check if given Graph is Strongly Connected or not
  10. Lexicographic sorting of given set of keys
  11. Find maximum occurring word in given set of strings
  12. Find first k maximum occurring words in given set of strings
  13. Find path from source to destination in a matrix that satisfies given constraints
  14. Find all occurrences of given string in a character matrix
  15. Flood Fill Algorithm
  16. Check if given Graph is Strongly Connected or not using one DFS Traversal
  17. Replace all occurrences of 0 that are not surrounded by 1 in a binary matrix
  18. Find Cost of Shortest Path in DAG using one pass of Bellman-Ford
  19. Traverse the given directory using BFS and DFS in Java


Thank you for being with us. 🙂


Leave a Reply

Notify of