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 –

- Depth First Search (DFS) | Iterative & Recursive Implementation

- Determine if a given graph is Bipartite Graph using DFS

- Topological Sorting in a DAG

- Transitive Closure of a Graph

- Check if an undirected graph contains cycle or not

- Determine if an undirected graph is a Tree (Acyclic Connected Graph)

- 2-Edge Connectivity in the graph

- Check if given digraph is a DAG (Directed Acyclic Graph) or not

- Check if given Graph is Strongly Connected or not

- Lexicographic sorting of given set of keys

- Find maximum occurring word in given set of strings

- Find first k maximum occurring words in given set of strings

- Find path from source to destination in a matrix that satisfies given constraints

- Find all occurrences of given string in a character matrix

- Flood Fill Algorithm

- Check if given Graph is Strongly Connected or not using one DFS Traversal

- Replace all occurrences of 0 that are not surrounded by 1 in a binary matrix

- Find Cost of Shortest Path in DAG using one pass of Bellman-Ford

- Traverse the given directory using BFS and DFS in Java

**Thank you for being with us. ðŸ™‚**

## Leave a Reply