Many Problems Become Graphs Once You Name the Nodes

Quick Revisit

• REACH FOR THIS WHEN: you suspect a problem hides a graph but the statement never says "graph"
• KEY DECISION: what are the nodes, what are the edges, and what are you computing?
• QUICK RULE: define nodes and edges on paper first -- the algorithm usually names itself
• SEE ALSO: Binary Search Reductions, Reduction Patterns

The moment you define nodes and edges, you inherit centuries of solved problems.

Prerequisites: BFS/DFS, Shortest Paths, MST

The Realization

Many competitive programming problems don't mention graphs. They talk about cities, transformations, tasks, games, friendships, grid cells. But underneath, a graph is often waiting to be named.

The trick isn't learning more graph algorithms. It's learning to see graphs where the problem doesn't advertise them — and, just as importantly, not forcing the lens onto problems that don't fit (see "Modeling overkill" below).

Five Problems That Are Secretly Graphs

1. Grid Shortest Path -> BFS on an Implicit Graph

Problem. Given a grid with obstacles, find the shortest path from top-left to bottom-right.

The reduction. You never build an adjacency list. Each cell (r, c) is a node. Its neighbors are the 4 adjacent cells without obstacles. Run BFS from (0, 0).

Why it works. BFS on an unweighted graph finds shortest paths. The grid is the graph -- you just never wrote it down explicitly.

int bfs(vector<string>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int,int>> q;
    q.push({0, 0}); dist[0][0] = 0;
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x+dx[d], ny = y+dy[d];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m
                && grid[nx][ny] != '#' && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return dist[n-1][m-1];
}

2. String Transformation -> BFS on State Space

Problem. Given a start word and end word, find the minimum number of single-character changes to transform one into the other. Each intermediate word must be in a dictionary.

• Nodes: words in the dictionary.
• Edges: two words are adjacent if they differ by exactly one character.
• Algorithm: BFS from start word. Distance to end word is the answer.

The graph might have ${10}^5$ nodes, but you never enumerate all $O(n^2)$ edges. Instead, for each word you generate its neighbors on the fly by trying all 26 replacements at each position.

3. Task Scheduling with Dependencies -> DAG + Topological Sort

Problem. Given $n$ tasks where some must finish before others can start, find a valid execution order (or report impossible).

• Nodes: tasks.
• Edges: directed edge from $A$ to $B$ means "$A$ must finish before $B$ starts."
• Algorithm: Topological sort. If the sorted order contains all $n$ tasks, it's valid. If not, there's a cycle -- impossible.

Need the earliest finish time for each task? Topo-sort, then DP forward: finish[v] = max(finish[u] + time[u]) over all predecessors $u$.

4. Two-Coloring Constraints -> Bipartiteness Check (or 2-SAT)

Problem. You have $n$ people. Some pairs hate each other. Can you split them into two groups so no two enemies share a group?

• Nodes: people.
• Edges: enmity relations.
• Algorithm: Check if the graph is bipartite (2-colorable) using BFS/DFS.

For more complex boolean constraints ("if Alice is in group 1, then Bob must be in group 2"), you're looking at 2-SAT: build an implication graph where each variable has two nodes (true/false), add implication edges, and check for consistency with SCCs.

5. Minimum Cost to Connect Components -> MST

Problem. You have $n$ cities and $m$ possible roads with costs. Find the cheapest way to connect all cities.

This one's almost too obvious -- but the reduction extends further than you'd think. What if the "cities" are pixels in an image and the "cost" is color difference? Same MST. What if you want the cheapest network of pipes, cables, or friendships? Same MST.

6. Game Positions -> DAG (Work Backwards)

Problem. Two players alternate moves. From a game state, certain moves are available. Who wins with optimal play?

• Nodes: game states.
• Edges: legal moves (directed, from current state to resulting state).
• Algorithm: When the game always terminates, the game graph is a DAG. Label terminal losing states, then work backwards: a state is winning if any child is losing; losing if all children are winning.

Loopy games. If states can repeat (the graph has cycles), backward induction on a DAG no longer applies directly. You either need a draw label (states that can force the game to loop forever), retrograde analysis (a worklist that propagates W/L from terminal states only as evidence allows), or game-specific machinery. Don't assume DAG without checking that moves strictly decrease some measure.

The Graph Modeling Checklist

Before you code, answer these three questions on paper:

Question	Why It Matters
What are your nodes?	Grid cells? States? People? Subsets? Time steps?
What are your edges?	Adjacency? Transitions? Dependencies? Conflicts?
What are you computing?	Shortest path? Connectivity? Ordering? Matching?

Once you've answered all three, the algorithm usually names itself.

The meta-insight: When you're stuck on a problem, don't ask "what algorithm should I use?" Ask "what is a node?" Everything else follows.

When the Graph Isn't Obvious

Some harder patterns to spot:

• Nodes are subsets. Bitmask DP is really shortest-path on a graph of $2^n$ states.
• Nodes are (position, time) pairs. Layered graphs model time-dependent costs.
• Nodes are (position, state) pairs. Carrying a key? Different edge set. Encode the key in the node.
• Edges have negative weights. You've moved from BFS/Dijkstra territory to Bellman-Ford.
• You need the k-th shortest path. Still a graph problem, just a harder graph algorithm.

Recognition Cues: When to Model as a Graph

If you see in the problem...	Think of this graph model	Algorithm family
Grid with obstacles, shortest path	Implicit grid graph, cells = nodes	BFS
Transform X into Y in minimum steps	State-space graph, states = nodes	BFS
Tasks with dependencies / prerequisites	DAG, tasks = nodes, deps = edges	Topological sort
Split into two groups with no conflicts	Undirected graph, bipartiteness check	BFS/DFS 2-coloring
Connect everything at minimum cost	Weighted graph, MST	Kruskal/Prim
Game positions, who wins with optimal play	DAG of game states, backward induction	Game DP on DAG
Nodes are subsets (n <= 20)	Bitmask state graph, 2^n nodes	Bitmask DP / BFS
Position + state pairs	Layered graph, (pos, state) = node	Dijkstra / BFS
Each node has exactly one outgoing edge	Functional graph	Cycle detection, binary lifting

Common Mistakes in Modeling

• Building the full adjacency list when you don't need to. For grid BFS or state-space BFS, generate neighbors on the fly. Materializing all edges wastes memory and time.
• Forgetting to encode constraints in the state. "Shortest path with a key" needs node = (position, keys_held). If you forget the key bitmask, you get wrong answers.
• Using Dijkstra on an unweighted graph. BFS is O(V+E); Dijkstra with a heap is O((V+E) log V). Don't pay the log factor for nothing.
• Assuming the graph is a DAG without checking. If the problem can have cycles, topological sort will fail silently (incomplete ordering). Always verify DAG structure or handle cycles.
• Modeling overkill. Not every problem with "connections" is a graph problem. Sometimes a simple DSU or even sorting suffices. Model at the right level of abstraction.

Cross-References

• BFS -- shortest path in unweighted graphs
• DFS -- cycle detection, topological sort
• Dijkstra -- weighted shortest paths
• MST -- minimum spanning trees
• Topological Sort -- DAG ordering
• BFS vs DFS Guide -- choosing traversal strategy
• Reduction Patterns -- the full "if X, think Y" catalog

Practice Problems

#	Problem	Source	Rating	Reduction
1	Shortest Path in Grid	CSES	1400	BFS on implicit grid graph
2	Word Ladder	LeetCode	1600	BFS on string-state graph
3	Course Schedule	LeetCode	1500	Cycle detection on a directed graph (DAG iff a topological order exists)
4	Is Graph Bipartite?	LeetCode	1500	2-coloring via BFS
5	Game on Graph	CF 936B	2000	Backward induction on game DAG

---

Recap

• Three questions before coding: What are the nodes? What are the edges? What are you computing?
• Grids, state spaces, task dependencies, games -- all secretly graphs once you name the nodes and edges.
• Don't build what you don't need: implicit graphs (generate neighbors on the fly) often suffice.
• Encode constraints in the node: keys, fuel, time -- anything that changes which edges are available belongs in the state.
• Once the graph is named, the algorithm follows: BFS for shortest path, topo-sort for ordering, MST for minimum connection cost.