Graphs
Nodes and edges generalizing trees to arbitrary connections — cycles, multiple parents, and disconnected components all allowed.
Try answering in your head first, then click a question to check the model answer.
Q1.When would you choose an adjacency matrix over an adjacency list for representing a graph?(show answer)
An adjacency matrix gives O(1) edge-existence lookup between any two specific nodes and is simple to implement, which is useful for dense graphs (many edges relative to nodes) or when you frequently need to check "is there an edge between A and B." But it uses O(V²) space regardless of how many edges actually exist, which wastes a lot of memory on sparse graphs — an adjacency list uses O(V + E) space and is the better default for most real-world (typically sparse) graphs.
Q2.Why does BFS guarantee the shortest path in an unweighted graph, while DFS does not?(show answer)
BFS explores the graph level by level — all nodes at distance 1 before any at distance 2, and so on — so the first time it reaches a node is guaranteed to be via the shortest possible path (fewest edges). DFS dives deep down one path before backtracking, so it can easily reach a node via a long, roundabout path first, with no guarantee that's the shortest one.
Q3.Why is tracking visited nodes essential for correctness in graph traversal, not just an optimization?(show answer)
Unlike a tree, a general graph can contain cycles — without marking nodes visited, a traversal could loop back to an already-processed node and recurse/iterate forever, never terminating. It's also an efficiency necessity even in acyclic graphs, since a node can be reachable via multiple paths and would otherwise be processed redundantly many times.
Q4.How would you detect a cycle in a directed graph using DFS?(show answer)
Track nodes in three states: unvisited, "currently in the recursion stack" (being explored), and "fully processed." If DFS encounters a node that's currently in the recursion stack (not just previously visited), that means there's a back edge to an ancestor in the current path — a cycle. This differs from undirected-graph cycle detection, which only needs a simple visited/unvisited distinction, since a directed graph can revisit an already-fully-processed node via a different path without that being a cycle.