BFS explores by edge distance when edges have equal cost. Marking nodes when enqueued avoids repeated queue entries.
Before you start
You should know arrays, loops and basic complexity notation. Start with a small input you can trace by hand. State what each variable means and which invariant is maintained, then use that invariant to explain correctness before discussing performance or writing a more compact solution.
The practical goal is to reason through this situation: The first discovered distance in an unweighted graph is shortest from the source. Read the walkthrough first, then try the interview exercise before opening its answer. The important part is explaining the decision and its consequences, rather than remembering a definition alone.
Step-by-step walkthrough
Step 1: Initialize the source
Distance zero belongs to the chosen starting node.
Step 2: Mark at enqueue time
Avoid inserting the same node through multiple neighbors.
Step 3: Explore by layers
Equal edge costs make the first discovered distance shortest.
Worked scenario
The first discovered distance in an unweighted graph is shortest from the source.
In a diamond graph, two neighbors both reach the same fourth node. Marking only when dequeued allows duplicate queue entries. Marking on insertion records its first distance once. Weighted edges invalidate the simple layer argument and require a different algorithm or restricted-weight method.
Common mistake
Using BFS for unequal weights can produce a wrong shortest path.
Verify the behavior
Test the diamond, disconnected nodes and an unequal-weight counterexample.
Interview exercise
Traverse a disconnected graph.
Answer and reasoning
Start from each unvisited component when full coverage is required, keeping source-distance semantics separate from component discovery.
Continue learning
Compare the scenario with the Data Structures and Algorithms interview questions and test your understanding with the Data Structures and Algorithms MCQs. For terminology and implementation details, consult the reference material.