Converting Problems to Graphs

One of the most powerful skills in algorithm design is the ability to see graphs where they aren't explicitly present. Many problems that seem unrelated to graphs—puzzles, optimization tasks, configuration problems—can be elegantly transformed into graph problems, unlocking decades of refined graph algorithms.

This transformation isn't trivial. It requires a trained eye to recognize relationships as edges, entities as vertices, and constraints as graph properties. But once mastered, this skill becomes a superpower—turning seemingly intractable problems into applications of well-known graph traversals, shortest paths, or connectivity algorithms.

Before diving into techniques, let's establish the fundamental mindset for graph modeling. At its core, a graph is nothing more than a representation of pairwise relationships. The key insight is this:

If your problem involves entities that have relationships with each other, there's likely a graph hiding inside.

This simple principle has profound implications. Consider:

• Entities become vertices (nodes)
• Relationships between entities become edges
• Relationship properties (costs, distances, capacities) become edge weights
• Entity properties (states, types) become vertex attributes

Converting a problem to a graph requires a structured approach. Here's a battle-tested framework used by experienced engineers and competitive programmers:

Step 1: Identify the Decision Space

Ask: "What am I trying to find or optimize?" The answer often reveals what your vertices should represent. If you're finding the shortest path between configurations, each configuration is a vertex. If you're finding the best sequence of actions, states resulting from actions are vertices.

Step 2: Define the Vertices Precisely

This is often the trickiest part. Vertices must encode all information needed to:

• Determine valid transitions (what edges exist)
• Evaluate the goal condition (are we at a destination?)
• Reconstruct the solution (trace back the path)

Ambiguity in vertex definition leads to broken algorithms.

Let's apply our framework to a classic problem that beautifully illustrates graph modeling:

The Word Ladder Problem:

Given two words beginWord and endWord, and a dictionary of words, find the length of the shortest transformation sequence from beginWord to endWord, where:

• Only one letter can be changed at a time
• Each transformed word must exist in the dictionary

Example:

• beginWord = "hit"
• endWord = "cog"
• dictionary = ["hot", "dot", "dog", "lot", "log", "cog"]
• Answer: 5 (hit → hot → dot → dog → cog)

At first glance, this looks nothing like a graph problem. There are no vertices, no edges, no paths mentioned. But let's apply our framework:

Why this works:

The insight is that we've reframed string manipulation as graph traversal. Instead of thinking about letter changes, we think about moving between connected vertices. The shortest transformation sequence is simply the shortest path in our implicitly defined graph.

This transformation is powerful because:

1. BFS guarantees the shortest path in an unweighted graph
2. The graph traversal abstraction separates the 'what' (find shortest path) from the 'how' (generate neighbors)
3. We can leverage decades of graph algorithm research instead of inventing a new algorithm

Let's examine a more directly graph-like problem, but one where the modeling choices still matter:

The Problem:

You're given a list of flights with source city, destination city, and price. Find the cheapest route from city A to city B with at most K stops.

Example:

• Flights: [("NYC", "CHI", 100), ("CHI", "LA", 200), ("NYC", "LA", 500)]
• From: NYC, To: LA, Max Stops: 1
• Answer: 300 (NYC → CHI → LA)

This problem explicitly involves connections, so the graph structure is more obvious. But the constraint "at most K stops" adds a twist that affects our vertex definition.

Key Modeling Insight:

Notice how the constraint fundamentally changed our vertex definition. Without it, each city appears once. With it, each city appears up to K+1 times (once for each possible "remaining stops" value).

This is a recurring pattern called state expansion or state augmentation:

• Base vertex: just the primary entity (city)
• Augmented vertex: entity + constraint-tracking state (city, stops remaining)

This pattern appears whenever:

• You have limited resources (fuel, time, budget)
• You must track usage counts (k stops, n operations)
• You have non-resettable state that affects future options

With practice, you'll develop an instinct for recognizing graph problems in disguise. Here are the telltale signals:

Signal 1: "Find the shortest/minimum/fastest way to get from A to B"

This screams shortest path. The question is: what's the graph?

Signal 2: "Can you reach state X from state Y?"

This is graph reachability—either BFS/DFS or connectivity check.

Signal 3: "In how many ways can you..." (with overlapping structure)

Often a DAG (Directed Acyclic Graph) where we count paths.

Signal 4: "Find all things connected to..." or "Group similar things"

Connected components or graph clustering.

Signal 5: "What order should we do things in?"

Topological sort on a dependency graph.

Over time, certain modeling patterns emerge repeatedly. Internalizing these patterns accelerates your problem-solving:

Pattern 1: State as Vertex

When a problem involves transitions between configurations or states, model each unique state as a vertex. Edges represent valid transitions.

Examples: Rubik's cube configurations, game board states, process states in scheduling.

Pattern 2: Entity as Vertex, Relationship as Edge

The most direct mapping—entities (people, places, objects) are vertices; relationships (knows, connects, flows) are edges.

Examples: Social networks, road networks, computer networks.

Pattern 3: Build Graph Explicitly vs Implicitly

For some problems, you build the entire graph upfront (adjacency list/matrix). For others—especially with large or infinite state spaces—you generate neighbors on-the-fly during traversal. This is called an implicit graph.

Explicit graph: When the graph is small and you'll do multiple queries on it. Implicit graph: When the state space is huge but you only explore a small fraction (e.g., puzzle solving with BFS).

We'll explore implicit graphs in depth on the next page.

To solidify your understanding, let's walk through how you would model several diverse problems as graphs:

Problem A: Minimum Genetic Mutation

A gene string is 8 characters from {A, C, G, T}. Given start gene, end gene, and a bank of valid genes, find minimum mutations to transform start to end.

Modeling:

• Vertices: Valid gene strings (in bank + start)
• Edges: Genes differing by exactly one character
• Algorithm: BFS for shortest path

Problem B: Open the Lock

A lock has 4 wheels, each with digits 0-9. From 0000, reach target, avoiding deadends.

Modeling:

• Vertices: All 4-digit combinations (excluding deadends)
• Edges: Combinations reachable by turning one wheel one step
• Algorithm: BFS from '0000' to target

Problem D: Course Schedule

Given n courses and prerequisites [[a,b],...] meaning 'b before a', determine if you can finish all courses.

Modeling:

• Vertices: Courses
• Edges: Directed edges from prerequisite to dependent course
• Problem: Can we complete all courses? = Is there a valid topological order? = Is the graph acyclic?
• Algorithm: Topological sort (detect cycle if impossible)

Problem E: Accounts Merge

Given accounts where each has a name and emails, merge accounts that share emails.

Modeling:

• Vertices: Emails
• Edges: Emails belonging to the same account are connected
• Problem: Find connected components of emails, group by component
• Algorithm: Union-Find or BFS for connected components