Graphs Problems

Graphs are the most general structure in computer science — anything with relationships fits the model — and graph problems are the most varied in interviews. Once you can fluently translate a problem into a graph (nodes, edges, weights), the algorithm catalog is small: BFS for shortest unweighted path, DFS for connectivity, topological sort for dependencies, union-find for dynamic connectivity, Dijkstra/Bellman-Ford for weighted shortest path.

The first skill is graph modeling — recognizing that "courses with prerequisites" is a DAG, "islands in a grid" is connected components, "cheapest flight" is weighted shortest path. The second is the right traversal — BFS over DFS depending on whether you need shortest path or just reachability. The third is state encoding — when the state is "(node, remaining-budget)" or "(row, col, direction)", search the expanded state space, not the raw graph.

The Ratta graph track covers Number of Islands, Clone Graph, Pacific Atlantic Water Flow, Course Schedule (cycle detection), Graph Valid Tree, Number of Connected Components, Alien Dictionary (topological sort with character ordering), and Word Ladder. Every problem includes the modeling step, the traversal choice, and complete implementations in C++, Java, Python, and Go.