BFS versus DFS
BFS explores equal-edge-distance layers using a queue, so first discovery gives a shortest path in edge count for unweighted graphs. DFS explores one branch deeply and can support cycle analysis or topological reasoning. Both require visited tracking for general graphs. Mark BFS vertices when they are enqueued to avoid redundant frontier entries. Iterative DFS avoids deep Java call stacks but needs an explicit stack and deliberate state handling.
Dependencies are directed
For Kahn topological sorting, count incoming edges, enqueue all zero-indegree vertices, emit them and decrement successors. If fewer than V vertices are emitted, a directed cycle remains. There may be many valid orders; an interview answer should not assume uniqueness. A priority queue can choose a deterministic smallest available vertex, but it changes the cost relative to an ordinary FIFO queue.
Weights change shortest-path reasoning
Dijkstra settles the vertex with the smallest tentative distance and relaxes outgoing nonnegative edges. That nonnegative condition is central to its correctness. A standard Java PriorityQueue implementation often inserts a new distance entry rather than decreasing a key, so discard stale entries when popped and account for the larger queue. For negative edges, consider an appropriate alternative such as Bellman–Ford, and discuss negative cycles.
Worked Java example
Illustrative snippet: imports, surrounding types or collaborators may be omitted. Read the assumptions before adapting it.
Queue<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
visited.add(source);
queue.add(source);
while (!queue.isEmpty()) {
int vertex = queue.remove();
for (int next : graph.getOrDefault(vertex, List.of())) {
if (visited.add(next)) queue.add(next);
}
}Walkthrough
When source reaches neighbors A and B, both become visited immediately. If A also points to B, the attempted add of B returns false, so B is not enqueued again. This makes each reachable vertex enter the queue once. To reconstruct a shortest unweighted route, record a predecessor at first discovery and trace backward from the destination.
Practice it yourself
Explain why ordinary BFS can choose the wrong cheapest route when one direct edge costs ten and a two-edge route costs one plus one.
Check your reasoning
BFS minimizes edge count and therefore favors the direct one-edge route. The cheaper route has two edges. With nonnegative weights use a weighted shortest-path algorithm; this example distinguishes hop count from total weight.
Recall checklist
- Explain the main invariant or contract without looking.
- Trace the example and test an edge case.
- State time, space, input variables and assumptions where relevant.
- Explain one alternative and when you would choose it.