Which graph traversal algorithm commonly uses a stack or recursion?

Options

  • A. BFS
  • B. DFS
  • C. Prim's algorithm
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

B. DFS

Detailed Explanation

Depth-First Search (DFS) explores a graph as deeply as possible before backtracking. It can be implemented using an explicit stack or through recursion, where the function call stack acts as the stack. DFS is useful for connected-component detection, cycle detection, topological sorting, and path exploration. Like BFS, DFS normally maintains a visited structure so that vertices are not processed repeatedly.