Question Bank
BFS vs DFS Fundamentals
Difficulty: Easy
Pin down the queue-vs-stack mechanics behind BFS and DFS, plus when level-by-level versus deep-first traversal is the right tool.
BFS vs DFS Fundamentals
Pin down the queue-vs-stack mechanics behind BFS and DFS, plus when level-by-level versus deep-first traversal is the right tool.
924 views
22
What data structure backs BFS, what data structure backs DFS, and what does each guarantee about visit order on an unweighted graph?
Implement iterative BFS that returns the visit order starting from src. The graph is an adjacency list of arrays.
Examples
Example 1:
Input: adj = [[1, 2], [0, 3], [0, 3], [1, 2]], src = 0
Output: [0, 1, 2, 3]
Explanation: Mark src visited before enqueuing, then loop while the queue is non-empty: pop the front, enqueue every unvisited neighbor while marking them visited at enqueue time. This stops the same node from being pushed multiple times.For the graph below, list the BFS visit order from vertex 0 and the DFS visit order from vertex 0 (DFS visits the first unvisited neighbor in each adjacency list).
Examples
Example 1:
Input: adj = {0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1, 5], 5: [2, 4]}, start = 0
Output: BFS visit order = [0, 1, 2, 3, 4, 5]; DFS visit order = [0, 1, 3, 4, 5, 2]
Explanation: BFS enqueues neighbors level by level. DFS descends to the first unvisited neighbor at each step (0 -> 1 -> 3, backtrack, 4, then 5, then 2). Sibling order is dictated by the adjacency list order.You need to find the shortest path in number of edges from one cell of a maze to another. Which traversal do you reach for, and what would go wrong if you used the other one?