How to Solve Graph Problems You've Never Seen
Learn how to solve graph problems with a 4-question approach that turns any unfamiliar problem into a clear algorithm choice.
Why graph problems feel harder than arrays or trees
A 4-question framework for approaching any graph problem
How to model grids, DAGs, and weighted networks as graphs
Common algorithm mismatches that cost you the problem
How to solve graph problems when you've never seen them before? Two engineers open the same problem. One stares at the description for ten minutes, writes nothing, and eventually guesses BFS. The other spends two minutes asking four questions, identifies it as a connected components task, and finishes a clean DFS solution with twelve minutes to spare.
They both know the same algorithms, so the difference isn't knowledge. One has a repeatable process for translating an unfamiliar problem into an algorithm choice. The other is matching against memory.
Why graph problems feel different
A graph problem is any problem where the solution depends on relationships between entities, whether those relationships are explicit (an edge list) or implicit (grid adjacency, dependency lists, network connections). That range of disguises is what makes them feel unpredictable. Graph problems aren't harder because the algorithms are more complex. They're harder because the modeling step is invisible.
With arrays, the data structure is given to you. You see an array, you think about two pointers or sliding windows. With trees, the structure is in the input. You see a root node with children, and traversal is the obvious starting point.
Graphs don't work that way. Most graph problems don't hand you an adjacency list. They hand you a grid, a list of dependencies, a network of cities, or a set of connections. Your first job isn't selecting an algorithm. It's recognizing that you're looking at a graph at all.
This is why knowing all five graph patterns doesn't prevent freezing on problems you haven't practiced. The translation from problem description to graph structure is where engineers actually get stuck.
Some graph problems (graph coloring, traveling salesman) are genuinely unsolvable in polynomial time, and the research on approximation algorithms for those is fascinating in its own right. But those rarely show up in coding interviews. Interview graph problems almost always map to one of five well known algorithms. The hard part is always the translation, not the algorithm.
Recognizing graphs hiding in plain sight
The modeling challenge gets easier once you've seen the common disguises. Graph problems rarely announce themselves. They show up wearing the costume of something else entirely.
- Grids: The most frequent disguise. A matrix of 0s and 1s looks like an array problem until you realize each cell connects to its neighbors. Any grid where you're asked about regions, paths, or reachability is a graph with
rows * colsnodes and up to four edges per node. - Dependency systems: Another common one. Course prerequisites, build systems, task scheduling, and package managers all describe directed graphs. When something "must come before" something else, you're looking at directed edges.
- State machines: They catch people off guard. Problems like "minimum moves to reach a target configuration" or "fewest button presses to unlock a combination" don't mention graphs anywhere. But each configuration is a node, and each valid move creates an edge to a new configuration. The entire state space forms an implicit graph, and the question "fewest moves" maps to BFS on that graph.
- Social networks: More obvious, but the edge definition still matters. "Are these two people in the same group?" is connectivity. "What's the shortest chain of introductions between two people?" is shortest path. Same entities, different properties, different algorithms.
Here's a quick recognition test you can run mentally on any problem:
- Does the problem involve entities that connect to other entities?
Probably a graph. - Does it ask about reaching one thing from another?
Almost certainly a graph. - Does it mention "minimum moves" or "fewest steps" between states?
That's BFS on an implicit graph. - Does it describe ordering constraints?
Topological sort on a DAG.
You don't need to memorize these patterns. You need to ask "what are the nodes and edges?" reflexively. If you can answer that question, you've already identified it as a graph problem.
How to solve graph problems with four questions
Every graph problem asks about a specific property, whether that's connectivity, shortest path, ordering, or cycles. Four repeatable questions turn unfamiliar problems into clear decisions. They work in order, and each one narrows the space for the next.
- 1What are the nodes?
Nodes are the individual entities or states, like people in a social network, cells in a grid, or courses in a dependency system. When the problem describes things that connect to other things, those things are your nodes. - 2What are the edges?
Edges define relationships between nodes. Are two cells adjacent? Is course A a prerequisite for course B? Can you fly from city X to city Y? After naming the edges, ask two follow ups. Are the edges directed (one way) or undirected? Do they carry weights (costs, distances, times)? - 3What property is the problem asking about?
This step gets skipped in favour of jumping straight to algorithms. Don't. Every graph problem targets one of five properties. - 4Which algorithm fits the property?
Naming the property narrows your algorithm choices from "everything you know" to two or three candidates. Once you know the property, selection is almost mechanical.
Python
Solve graph problems in practice with counting islands
This doesn't look like a graph problem at first. There's no edge list and no mention of nodes. But watch what happens when you run the four questions.
Nodes are each cell in the grid. Edges connect two cells if they're adjacent (up, down, left, right) and both contain 1. The edges are undirected and unweighted.
Property is "how many groups?" That's connectivity, specifically the number of connected components.
Algorithm is DFS or BFS from any unvisited 1. Traverse all reachable 1s, mark them visited, increment the count. Repeat until no unvisited 1s remain.
The whole problem collapses once you name the property. You didn't need to memorize "island count equals connected components." You needed to recognize that "how many groups of connected things" is always a connectivity question. The algorithm followed from the property, not from having seen this exact problem before.
“You didn't need to memorize that island count equals connected components. You needed to recognize that 'how many groups' is always a connectivity question.”
Two more problems, same four questions
Course prerequisites
Courses are your nodes, and prerequisites create directed edges: if course 0 must come before course 1, draw an edge from 0 to 1. The question "can everything be ordered?" is an ordering problem, which means topological sort. If the sort processes all n nodes, the answer is yes. If it can't, a cycle exists and the answer is no. The cycle check comes free here, since a directed graph has a valid topological order if and only if it contains no cycles.
Cheapest flights with at most K stops
Cities are your nodes, and flights are directed, weighted edges. The question is shortest path, but with a constraint: maximum K edges in the path.
Your first instinct might be Dijkstra's. But Dijkstra greedily picks the cheapest next node without tracking how many edges you've used. The K stops constraint means path length matters, not just cost. A better fit: BFS processing one level per stop, or Bellman-Ford run for exactly K+1 iterations.
Naming the constraint before selecting the algorithm prevented a Dijkstra implementation that would've needed awkward modification mid solve. Two minutes of thinking saved ten minutes of debugging.
Common mismatches when solving graph problems
Even with the four questions, certain mistakes keep showing up. Worth knowing what they are so you can catch them faster.
- BFS vs DFS confusion: BFS finds shortest paths in unweighted graphs. DFS explores deeply, not optimally, and doesn't guarantee shortest paths. If the problem asks for "minimum steps" or "fewest moves," that's BFS. If it asks for "all paths" or "does any path exist," DFS is simpler. Our BFS vs DFS comparison walks through the full decision process.
- Dijkstra and negative weights: Dijkstra only works with non negative edge weights. If a problem involves penalties or negative costs, Dijkstra can return wrong answers silently, with no error to alert you. Bellman-Ford handles negative weights correctly but runs in
O(V * E)instead ofO((V + E) log V). - Wrong representation choice: Adjacency lists use
O(V + E)space and work well for sparse graphs, which covers most interview problems. Adjacency matrices useO(V²)and make sense for dense graphs or when you need constant time edge lookups. For grid problems, the grid itself is the representation. Don't convert it to an adjacency list unless the problem specifically requires it.
Edge cases that trip up experienced engineers
The four question framework gets you to the right algorithm. But graph problems have a handful of recurring edge cases that can break a correct algorithm if you don't account for them upfront.
- Disconnected graphs: Not every graph is one connected piece. If you run a single BFS or DFS from one starting node, you'll miss entire components. For problems that ask about all nodes (counting components, checking if every course can be taken), you need an outer loop that starts a new traversal from each unvisited node.
- Self-loops and parallel edges: Some problems include edges from a node to itself or multiple edges between the same pair of nodes. These won't crash your code, but they can produce wrong answers in cycle detection or shortest path calculations if you're not careful. Check the problem constraints for whether duplicate edges or self-loops are possible.
- Empty or single node graphs: What happens when the graph has zero edges? Or just one node? These are the cases your algorithm handles correctly only if you've thought about them. A connected components count on an empty grid should return 0. A shortest path query on a single node with no edges should return 0 if source equals destination.
- Visited state management: In undirected graphs, a simple
visitedset is enough. In directed graphs, especially for cycle detection, you need three states: unvisited, in progress (currently on the recursion stack), and fully processed. Using only two states causes false positives where a node visited via a different path gets flagged as a cycle. - Integer overflow: When you're summing edge weights for shortest path calculations, the accumulated cost can exceed standard integer limits in some languages. If the problem specifies large weights or a large number of edges, keep an eye on your running totals. Initializing distances to
float('inf')in Python avoids this, but in Java or C++ you'll want to be more deliberate about your sentinel values.
These aren't obscure corner cases. They show up in roughly a third of graph interview problems. Spending thirty seconds mentally checking for them after you've picked your algorithm saves you from the kind of bugs that eat ten minutes of debugging time.
Think before you implement
The four questions work because they force you to think about the problem before the solution. Every pattern module in Codeintuition's graph course follows the same principle: understand the mechanism, learn to identify when it applies, then solve problems with increasing difficulty. The identification lesson for connected components, for example, teaches the signals that distinguish a connectivity problem from a shortest path problem before you attempt a single problem.
One more thing worth practicing: mentally trace the algorithm on a specific input before writing code. Walk through BFS on your grid and predict the traversal order node by node. You'll catch edge cases before your first submission.
The same identification first approach works across all of DSA.
For dynamic programming, a similar three part identification test determines whether a problem needs DP before you start building a recurrence. Map the problem before you solve it.
You can try the full teaching approach before deciding whether it fits how you learn. The first two courses (Arrays and Singly Linked List) are free and use the same identification first method that the Graph course builds on. The complete learning path is $79.99/year.
Think about the last time you opened a graph problem. You probably read the description three times and started coding BFS because it's the algorithm you remembered best. Now picture this instead: you spend two minutes naming nodes, edges, and the property. The algorithm falls out naturally, and you haven't written a line of code yet. That's the shift.
Want to learn the four questions on real graph problems?
Codeintuition's Graph course teaches connected components, shortest path, and topological sort with identification triggers before every problem set. Start with the FREE Arrays course to build the foundation