Question 1

What is the difference between Breadth-First Search (BFS) and Depth-First Search (DFS)?

Accepted Answer

BFS explores the graph layer by layer, using a queue to keep track of the nodes to visit. It is often used to find the shortest path in an unweighted graph. DFS explores the graph by going as deep as possible along each branch before backtracking, using a stack (or recursion) to keep track of the nodes. It is used in problems like cycle detection and topological sorting.

Question 2

How do you detect a cycle in a directed graph using DFS?

Accepted Answer

To detect a cycle in a directed graph, you can use DFS with two sets of visited nodes: one for the current recursion stack and one for all visited nodes. If you encounter a node that is already in the current recursion stack during DFS, you have found a cycle.

Graph Traversal Algorithms Interview Questions

Related Algorithm Guides