intermediate
Graphs
Vertices, edges, adjacency structures, directedness, weights, and traversal implications.
Graphs model relationships through vertices and edges. Before choosing BFS, DFS, or shortest path, decide whether edges are directed, weighted, cyclic, sparse, or dense. The representation matters: adjacency lists are common for sparse graphs, while matrices simplify constant-time edge checks.
On interviews: Good answers first build the graph from input, then state visited handling, traversal order, and complexity in terms of V and E.
Common pitfalls: Forgetting visited tracking causes infinite loops on cycles. Rebuilding neighbors repeatedly can hide extra cost. Weighted graphs often need Dijkstra, not plain BFS.
Checklist:
- Define V and E.
- Choose adjacency representation.
- Track visited state.
- Match traversal to edge weights.