Graphs

Graphs are the universal modeling structure — any relationship between objects can be represented as a graph. The two fundamental traversals (BFS and DFS) solve an enormous range of problems. BFS is optimal for shortest paths in unweighted graphs (explores layer by layer). DFS excels at exhaustive search (connected components, cycle detection, topological sort). Union-Find is the elegant structure for dynamic connectivity. Dijkstra extends BFS with weights. Internalize these five tools and you can tackle ~90% of graph interview problems. Understanding Graphs A graph is a collection of nodes (vertices) connected by edges. Graphs model relationships: social networks, maps, dependencies, web links. They're the most versatile data structure. Representations: Adjacency list: Map<node, List<neighbor— best for sparse graphs, O(V+E) space Adjacency matrix: boolean[V][V] — best for dense graphs, O(V²) space Key algorithms: BFS: shortest path (unweighted), level-order exploration — uses queue DFS: cycle detection, topological sort, connected components — uses stack/recursion Dijkstra's: shortest path (weighted, non-negative) — uses priority queue Topological sort: ordering with dependencies — DFS or Kahn's (BFS with indegree) Union-Find: connected components, cycle detection — uses disjoint set Interview tips: Always clarify: directed vs undirected? weighted? cycles? connected? Start with the simplest approach (BFS/DFS), then optimize Watch for disconnected graphs — iterate over all nodes Graphs Graphs model relationships between entities. Master BFS, DFS, topological sort, and shortest path algorithms. Representations Topological Sort (Course Schedule) Dijkstra's Shortest Path Key Problems #200 Number of Islands, #207 Course Schedule #133 Clone Graph, #743 Network Delay Time (Dijkstra) Interview Tip "For graph problems, I first determine: directed vs undirected? weighted vs unweighted? Then I choose the algorithm: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for dependencies." Java Implementation: