Graph Exercises: Practice Problems (with Solutions)
Time to put the graph algorithms to work. Solve each problem yourself first — pick a representation, decide between BFS and DFS, and reason about the time and space complexity before writing code. Only then open the answer sheet. Every View answer link jumps to a full multi-language solution on the graph solutions page.
How to practice: Set a timer (20–30 min per problem). If you’re stuck, revisit the relevant concept page — BFS, DFS, topological sort, or Dijkstra — before peeking.
Warm-ups
Q1. Number of Islands. Given an m × n grid of '1' (land) and '0' (water), count the islands. An island is land connected horizontally or vertically. Target O(m·n) time. This is connected components on an implicit grid graph.
Q2. Flood Fill. Given an image grid, a starting pixel, and a new color, recolor the starting pixel and every 4-directionally connected pixel of the same original color. Return the modified image.
Core problems
Q3. Clone Graph. Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the whole graph. Each node holds a value and a list of neighbors. Avoid infinite loops on cycles.
Q4. Course Schedule. There are numCourses courses labeled 0..numCourses-1 and a list of prerequisite pairs [a, b] meaning you must take b before a. Return true if you can finish all courses — i.e., the dependency graph is a DAG. Use cycle detection or topological sort.
Q5. Word Ladder. Given beginWord, endWord, and a word list, find the length of the shortest transformation sequence where each step changes exactly one letter and every intermediate word is in the list. Return 0 if impossible. Hint: shortest path on an unweighted graph.
Challenge
Q6. Network Delay Time. A network has n nodes labeled 1..n and directed travel times times[i] = [u, v, w]. Sending a signal from node k, return the time for all nodes to receive it, or -1 if some node never does. This is single-source shortest path — reach for Dijkstra.
Q7. Cheapest Flights Within K Stops. Given n cities, a list of flights [from, to, price], source src, destination dst, and an integer k, return the cheapest price from src to dst using at most k stops, or -1. Hint: a bounded-relaxation variant of Bellman-Ford.
Done? Review every solution on the graph answer sheet — even the ones you solved, since there’s often a cleaner approach. Then continue to greedy algorithms.