The model
A graph models entities as vertices and relationships as edges. Before choosing an algorithm, decide whether edges are directed, weighted, duplicated, or allowed to change. Those choices affect both the meaning of a path and the representation needed to answer queries efficiently.
A concrete walk-through
An adjacency list stores each vertex with its outgoing neighbors, so scanning all neighbors costs in proportion to the degree. Breadth-first search uses a queue and discovers vertices in increasing edge distance for an unweighted graph. Depth-first search follows one branch until it must backtrack, which is useful for reachability and cycle reasoning.
Costs and failure cases
An adjacency matrix uses quadratic space but makes edge existence checks constant time and can be effective for dense graphs. BFS does not find a minimum-cost path when edge weights differ; Dijkstra requires nonnegative weights, while negative edges need other methods. Marking a node visited at the right time prevents duplicate queue growth.
Check your understanding
For a directed graph with an unreachable component, describe how you would count components and why one traversal from a single start node is insufficient.