Back to the full dot-point answer
SingaporeComputer ScienceQuick questions
Algorithms and Problem Solving
Quick questions on Graph traversal with BFS and DFS explained: H2 Computing
5short Q&A pairs drawn directly from our worked dot-point answer. For full context and worked exam questions, read the parent dot-point page.
What is breadth-first search (BFS)?Show answer
BFS uses a queue (first in, first out). It visits a node, enqueues its unvisited neighbours, then dequeues the next node - so it fans out level by level from the start:
What is depth-first search (DFS)?Show answer
DFS uses a stack (last in, first out), or recursion via the call stack. It goes as deep as possible along one path, then backtracks:
What is q1?Show answer
Which data structure drives breadth-first search, and which drives depth-first search? [2 marks]
What is q2?Show answer
Why does BFS find the shortest path (in edges) in an unweighted graph? [2 marks]
What is q3?Show answer
Give one task for which depth-first search is better suited than breadth-first search. [1 mark]
Have a question we have not covered?
This dot-point answer is short enough that we have not extracted many short questions yet. Read the full dot-point answer or ask Mo, our study assistant, in the chat for follow ups.