Converting Problems to Graphs - Common Graph Modeling Patterns | OneNoughtOne

0/361

Data Structures & AlgorithmsGraph Modeling Patterns

Common Graph Modeling Patterns

LevelIntermediate

Duration60 mins

TopicGraph Modeling Patterns

1 / 4

Converting Problems to Graphs

The Hidden Graph in Every Problem

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.

What You Will Learn

By the end of this page, you will understand how to systematically identify graph structures in problems that don't explicitly mention graphs. You'll learn to define vertices and edges, recognize implicit graph structures, and apply this modeling technique to solve problems ranging from word puzzles to flight planning to social network analysis.

The Graph Modeling Mindset

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

From Problem Domain to Graph Components
Problem Domain	Entities → Vertices	Relationships → Edges	Properties → Weights
Social Network	People	Friendships	Interaction frequency
Road Network	Intersections	Roads	Distance or travel time
Flight Planning	Cities/Airports	Direct flights	Flight duration or cost
Word Ladder Puzzle	Words	Differ by one letter	Number of changes
Task Scheduling	Tasks	Dependencies	Time to complete
Web Crawling	Web pages	Hyperlinks	Link relevance

The Universal Question

When faced with any problem, ask yourself: 'What are the things (vertices)? What connects them (edges)? What's important about those connections (weights)?' These three questions form the foundation of all graph modeling.

A Systematic Conversion Framework

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.

Step-by-Step Conversion Process

•Identify candidate vertices — What are the 'states' or 'configurations' in your problem?
•Define vertex equality — When are two vertices the same? What uniquely identifies a state?
•Define edges — What transitions exist? What connects one state to another?
•Determine edge directionality — Are relationships symmetric (undirected) or one-way (directed)?
•Assign edge weights — Do transitions have costs, distances, or priorities?
•Identify start and goal vertices — Where do we begin? What constitutes 'solved'?
•Choose the right graph algorithm — BFS for unweighted shortest path, Dijkstra for weighted, DFS for exploration, etc.

Common Pitfall: Insufficient State Encoding

A frequent mistake is not including enough information in the vertex definition. For example, in a maze where you can pick up keys, the vertex isn't just (row, col)—it's (row, col, keys_collected). Missing state components leads to incorrect algorithms that visit 'different' states as if they were the same.

Case Study: The Word Ladder Problem

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:

Applying the Conversion Framework

•Vertices: Each word in the dictionary (including beginWord) is a vertex
•Edges: Two words are connected if they differ by exactly one letter
•Directionality: Undirected—if 'hot' can become 'dot', 'dot' can become 'hot'
•Weights: All edges have weight 1 (one transformation step)
•Start vertex: beginWord ('hit')
•Goal vertex: endWord ('cog')
•Algorithm choice: BFS—we want shortest path in an unweighted graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from collections import deque
from typing import List, Set
 
def word_ladder(begin_word: str, end_word: str, word_list: List[str]) -> int:
    """
    Find the shortest transformation sequence length using BFS on an implicit graph.
    
    Time Complexity: O(N × M²) where N = number of words, M = word length
    Space Complexity: O(N × M) for the word set and queue
    """
    # Build the vertex set (dictionary + begin word)
    word_set: Set[str] = set(word_list)
    if end_word not in word_set:
        return 0  # Goal vertex doesn't exist in graph
    
    # Edge definition: words differing by exactly one letter
    def get_neighbors(word: str) -> List[str]:
        """Find all vertices (words) connected to this vertex by an edge."""
        neighbors = []
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if c != word[i]:
                    # Create a word differing by one character at position i
                    new_word = word[:i] + c + word[i+1:]
                    if new_word in word_set:
                        neighbors.append(new_word)
        return neighbors
    
    # BFS to find shortest path in unweighted graph
    queue = deque([(begin_word, 1)])  # (current_vertex, path_length)
    visited = {begin_word}
    
    while queue:
        current_word, distance = queue.popleft()
        
        # Check if we've reached the goal vertex
        if current_word == end_word:
            return distance
        
        # Explore all neighboring vertices (words differing by one letter)
        for neighbor in get_neighbors(current_word):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))
    
    return 0  # No path exists from start to goal
 
# Example usage
begin_word = "hit"
end_word = "cog"
word_list = ["hot", "dot", "dog", "lot", "log", "cog"]
result = word_ladder(begin_word, end_word, word_list)
print(f"Shortest transformation: {result} steps")  # Output: 5

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:

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

Case Study: Cheapest Flight Routing

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.

The Constraint Changes Everything

Without the K-stop constraint, vertices would simply be cities. But with the constraint, we need to track how many stops we've used. This leads to an expanded state space where vertices are (city, stops_remaining) pairs—a classic pattern in constrained graph problems.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import heapq
from typing import List, Tuple, Dict
 
def find_cheapest_flight(
    flights: List[Tuple[str, str, int]], 
    src: str, 
    dst: str, 
    k: int
) -> int:
    """
    Find cheapest route with at most k stops using modified Dijkstra's.
    
    Vertex definition: (city, stops_remaining)
    Edge definition: direct flights between cities
    Edge weight: flight price
    
    Time Complexity: O(E × K × log(V × K))
    Space Complexity: O(V × K) for the expanded state space
    """
    # Build adjacency list: city -> [(destination, price), ...]
    graph: Dict[str, List[Tuple[str, int]]] = {}
    for from_city, to_city, price in flights:
        if from_city not in graph:
            graph[from_city] = []
        graph[from_city].append((to_city, price))
    
    # State: (total_cost, city, stops_remaining)
    # Priority queue for Dijkstra's algorithm
    # k+1 because k stops means k+1 flights
    pq = [(0, src, k + 1)]  
    
    # Track best cost to reach each (city, stops) state
    # This prevents revisiting worse states
    best: Dict[Tuple[str, int], int] = {}
    
    while pq:
        cost, city, remaining = heapq.heappop(pq)
        
        # Goal check: reached destination?
        if city == dst:
            return cost
        
        # Skip if we've seen this state with lower cost
        if (city, remaining) in best:
            continue
        best[(city, remaining)] = cost
        
        # Can't expand if no stops remaining
        if remaining == 0:
            continue
        
        # Explore all outgoing edges (flights from this city)
        for next_city, price in graph.get(city, []):
            new_cost = cost + price
            new_state = (next_city, remaining - 1)
            
            # Only explore if we haven't found a better path to this state
            if new_state not in best:
                heapq.heappush(pq, (new_cost, next_city, remaining - 1))
    
    return -1  # No valid route exists
 
# Example usage
flights = [("NYC", "CHI", 100), ("CHI", "LA", 200), ("NYC", "LA", 500)]
result = find_cheapest_flight(flights, "NYC", "LA", 1)
print(f"Cheapest route: ${result}")  # Output: 300

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

Recognizing Hidden Graph Problems

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.

Problem Phrases and Their Graph Interpretation
Problem Phrase	Graph Interpretation	Algorithm
Shortest path from A to B	Find minimum edge path	BFS (unweighted) / Dijkstra (weighted)
Minimum cost to transform	Weighted shortest path	Dijkstra / Bellman-Ford
Is it possible to reach...	Path existence / Reachability	BFS / DFS
Find all connected items	Connected components	Union-Find / BFS
Optimal ordering of tasks	Topological sort	Kahn's algorithm / DFS
Cycle detection	Does a cycle exist?	DFS with coloring / Union-Find
Minimum connections needed	Minimum spanning tree	Kruskal / Prim
Maximum flow/matching	Flow network	Ford-Fulkerson

The Transformation Principle

When you see 'transform A to B' or 'convert X to Y', think graphs. Each valid state is a vertex, each valid transformation is an edge. Finding the minimum/optimal transformation is finding the shortest/optimal path.

Common Graph Modeling Patterns

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.

Vertex Modeling Patterns

•State Vertex: Complete configuration of the problem
•Entity Vertex: Physical or logical entities
•Time-Expanded Vertex: (entity, time) pairs for temporal problems
•Augmented Vertex: Entity + constraint state
•Event Vertex: Discrete events in a sequence

Edge Modeling Patterns

•Transition Edge: Valid state changes
•Relationship Edge: Connections between entities
•Similarity Edge: Entities with shared properties
•Dependency Edge: X must precede Y
•Flow Edge: Capacity between points

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.

Applying the Framework: Practice Problems

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 C: Sliding Puzzle

Given a 2x3 board with tiles 1-5 and one empty space (0), slide tiles to reach the goal state [[1,2,3],[4,5,0]]. Minimum moves?

Modeling:

Vertices: Board configurations (can use tuple of tuple for hashability)
Edges: Configurations reachable by one tile slide
Algorithm: BFS for shortest path

This is a classic example where the graph is implicit—you don't precompute all 6! = 720 configurations; you generate neighbors during BFS.

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

Summary: The Art of Graph Modeling

The ability to convert problems to graphs is a fundamental skill that opens up a vast toolkit of efficient algorithms. Let's consolidate what we've learned:

Key Takeaways

•Graphs are universal — Any problem with entities and relationships can potentially be modeled as a graph.
•Vertex definition is critical — Include enough state to capture the problem, but not so much that you explode the state space.
•Edges encode transitions — What moves are valid? How do we get from one state to another?
•Constraints often expand state — Tracking resources, limits, or counts may require augmented vertices.
•Implicit graphs enable huge state spaces — Generate neighbors on-the-fly instead of building the full graph.
•Pattern recognition accelerates modeling — With practice, you'll recognize 'this is a shortest path problem' immediately.
•The algorithm follows the model — Once the graph is defined, choosing the right algorithm often becomes straightforward.

What's Next:

Now that you understand explicit graph modeling, the next page explores implicit graphs and state spaces—a powerful technique for handling problems with enormous or even infinite state spaces without constructing the entire graph in memory.

Page Complete

You now understand how to systematically convert problems into graph representations. This skill transforms seemingly unrelated problems into applications of well-studied graph algorithms. Next, we'll explore implicit graphs—the technique for handling massive state spaces efficiently.

Data Structures & AlgorithmsGraph Modeling Patterns

Common Graph Modeling Patterns

LevelIntermediate

Duration60 mins

TopicGraph Modeling Patterns

1 / 4

Converting Problems to Graphs

The Hidden Graph in Every Problem

What You Will Learn

The Graph Modeling Mindset

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

From Problem Domain to Graph Components
Problem Domain	Entities → Vertices	Relationships → Edges	Properties → Weights
Social Network	People	Friendships	Interaction frequency
Road Network	Intersections	Roads	Distance or travel time
Flight Planning	Cities/Airports	Direct flights	Flight duration or cost
Word Ladder Puzzle	Words	Differ by one letter	Number of changes
Task Scheduling	Tasks	Dependencies	Time to complete
Web Crawling	Web pages	Hyperlinks	Link relevance

The Universal Question

A Systematic Conversion Framework

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

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.

Step-by-Step Conversion Process

•Identify candidate vertices — What are the 'states' or 'configurations' in your problem?
•Define vertex equality — When are two vertices the same? What uniquely identifies a state?
•Define edges — What transitions exist? What connects one state to another?
•Determine edge directionality — Are relationships symmetric (undirected) or one-way (directed)?
•Assign edge weights — Do transitions have costs, distances, or priorities?
•Identify start and goal vertices — Where do we begin? What constitutes 'solved'?
•Choose the right graph algorithm — BFS for unweighted shortest path, Dijkstra for weighted, DFS for exploration, etc.

Common Pitfall: Insufficient State Encoding

Case Study: The Word Ladder Problem

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:

Applying the Conversion Framework

•Vertices: Each word in the dictionary (including beginWord) is a vertex
•Edges: Two words are connected if they differ by exactly one letter
•Directionality: Undirected—if 'hot' can become 'dot', 'dot' can become 'hot'
•Weights: All edges have weight 1 (one transformation step)
•Start vertex: beginWord ('hit')
•Goal vertex: endWord ('cog')
•Algorithm choice: BFS—we want shortest path in an unweighted graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from collections import deque
from typing import List, Set
 
def word_ladder(begin_word: str, end_word: str, word_list: List[str]) -> int:
    """
    Find the shortest transformation sequence length using BFS on an implicit graph.
    
    Time Complexity: O(N × M²) where N = number of words, M = word length
    Space Complexity: O(N × M) for the word set and queue
    """
    # Build the vertex set (dictionary + begin word)
    word_set: Set[str] = set(word_list)
    if end_word not in word_set:
        return 0  # Goal vertex doesn't exist in graph
    
    # Edge definition: words differing by exactly one letter
    def get_neighbors(word: str) -> List[str]:
        """Find all vertices (words) connected to this vertex by an edge."""
        neighbors = []
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if c != word[i]:
                    # Create a word differing by one character at position i
                    new_word = word[:i] + c + word[i+1:]
                    if new_word in word_set:
                        neighbors.append(new_word)
        return neighbors
    
    # BFS to find shortest path in unweighted graph
    queue = deque([(begin_word, 1)])  # (current_vertex, path_length)
    visited = {begin_word}
    
    while queue:
        current_word, distance = queue.popleft()
        
        # Check if we've reached the goal vertex
        if current_word == end_word:
            return distance
        
        # Explore all neighboring vertices (words differing by one letter)
        for neighbor in get_neighbors(current_word):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))
    
    return 0  # No path exists from start to goal
 
# Example usage
begin_word = "hit"
end_word = "cog"
word_list = ["hot", "dot", "dog", "lot", "log", "cog"]
result = word_ladder(begin_word, end_word, word_list)
print(f"Shortest transformation: {result} steps")  # Output: 5

Why this works:

This transformation is powerful because:

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

Case Study: Cheapest Flight Routing

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.

The Constraint Changes Everything

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import heapq
from typing import List, Tuple, Dict
 
def find_cheapest_flight(
    flights: List[Tuple[str, str, int]], 
    src: str, 
    dst: str, 
    k: int
) -> int:
    """
    Find cheapest route with at most k stops using modified Dijkstra's.
    
    Vertex definition: (city, stops_remaining)
    Edge definition: direct flights between cities
    Edge weight: flight price
    
    Time Complexity: O(E × K × log(V × K))
    Space Complexity: O(V × K) for the expanded state space
    """
    # Build adjacency list: city -> [(destination, price), ...]
    graph: Dict[str, List[Tuple[str, int]]] = {}
    for from_city, to_city, price in flights:
        if from_city not in graph:
            graph[from_city] = []
        graph[from_city].append((to_city, price))
    
    # State: (total_cost, city, stops_remaining)
    # Priority queue for Dijkstra's algorithm
    # k+1 because k stops means k+1 flights
    pq = [(0, src, k + 1)]  
    
    # Track best cost to reach each (city, stops) state
    # This prevents revisiting worse states
    best: Dict[Tuple[str, int], int] = {}
    
    while pq:
        cost, city, remaining = heapq.heappop(pq)
        
        # Goal check: reached destination?
        if city == dst:
            return cost
        
        # Skip if we've seen this state with lower cost
        if (city, remaining) in best:
            continue
        best[(city, remaining)] = cost
        
        # Can't expand if no stops remaining
        if remaining == 0:
            continue
        
        # Explore all outgoing edges (flights from this city)
        for next_city, price in graph.get(city, []):
            new_cost = cost + price
            new_state = (next_city, remaining - 1)
            
            # Only explore if we haven't found a better path to this state
            if new_state not in best:
                heapq.heappush(pq, (new_cost, next_city, remaining - 1))
    
    return -1  # No valid route exists
 
# Example usage
flights = [("NYC", "CHI", 100), ("CHI", "LA", 200), ("NYC", "LA", 500)]
result = find_cheapest_flight(flights, "NYC", "LA", 1)
print(f"Cheapest route: ${result}")  # Output: 300

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

Recognizing Hidden Graph Problems

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.

Problem Phrases and Their Graph Interpretation
Problem Phrase	Graph Interpretation	Algorithm
Shortest path from A to B	Find minimum edge path	BFS (unweighted) / Dijkstra (weighted)
Minimum cost to transform	Weighted shortest path	Dijkstra / Bellman-Ford
Is it possible to reach...	Path existence / Reachability	BFS / DFS
Find all connected items	Connected components	Union-Find / BFS
Optimal ordering of tasks	Topological sort	Kahn's algorithm / DFS
Cycle detection	Does a cycle exist?	DFS with coloring / Union-Find
Minimum connections needed	Minimum spanning tree	Kruskal / Prim
Maximum flow/matching	Flow network	Ford-Fulkerson

The Transformation Principle

Common Graph Modeling Patterns

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.

Vertex Modeling Patterns

•State Vertex: Complete configuration of the problem
•Entity Vertex: Physical or logical entities
•Time-Expanded Vertex: (entity, time) pairs for temporal problems
•Augmented Vertex: Entity + constraint state
•Event Vertex: Discrete events in a sequence

Edge Modeling Patterns

•Transition Edge: Valid state changes
•Relationship Edge: Connections between entities
•Similarity Edge: Entities with shared properties
•Dependency Edge: X must precede Y
•Flow Edge: Capacity between points

Pattern 3: Build Graph Explicitly vs Implicitly

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.

Applying the Framework: Practice Problems

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 C: Sliding Puzzle

Given a 2x3 board with tiles 1-5 and one empty space (0), slide tiles to reach the goal state [[1,2,3],[4,5,0]]. Minimum moves?

Modeling:

Vertices: Board configurations (can use tuple of tuple for hashability)
Edges: Configurations reachable by one tile slide
Algorithm: BFS for shortest path

This is a classic example where the graph is implicit—you don't precompute all 6! = 720 configurations; you generate neighbors during BFS.

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

Summary: The Art of Graph Modeling

The ability to convert problems to graphs is a fundamental skill that opens up a vast toolkit of efficient algorithms. Let's consolidate what we've learned:

Key Takeaways

•Graphs are universal — Any problem with entities and relationships can potentially be modeled as a graph.
•Vertex definition is critical — Include enough state to capture the problem, but not so much that you explode the state space.
•Edges encode transitions — What moves are valid? How do we get from one state to another?
•Constraints often expand state — Tracking resources, limits, or counts may require augmented vertices.
•Implicit graphs enable huge state spaces — Generate neighbors on-the-fly instead of building the full graph.
•Pattern recognition accelerates modeling — With practice, you'll recognize 'this is a shortest path problem' immediately.
•The algorithm follows the model — Once the graph is defined, choosing the right algorithm often becomes straightforward.

What's Next:

Page Complete