Graphs: how to spot it
We'll cover the following
A graph is things (nodes) joined by connections (edges). You mostly traverse it, order it, group it, or find cheapest routes through it.
How the question sounds
- Tasks with prerequisites or dependencies: topological sort
- Are these two things connected, or how many groups are there: union-find or DFS
- Cheapest or shortest route with different costs: Dijkstra
- Detect a cycle in dependencies
- Words like network, courses, provinces, or routes
The two shapes
Where it shows up in GenAI work
Agent and RAG pipelines are DAGs, so you run steps in topological order and reject circular dependencies. GraphRAG traverses a knowledge graph. Union-find groups near-duplicate documents, and shortest-path ideas appear in cost-aware routing between models and tools.
Is it graphs?
Decide yes or no before you open each answer.
Check yourselfOrder courses so every prerequisite comes first.
Yes. Topological sort on a dependency graph.
Check yourselfFind the cheapest route between two cities with different road lengths.
Yes. Weighted shortest path: Dijkstra.
Check yourselfCount how many separate friend groups exist.
Yes. Connected components: union-find or DFS.
Check yourselfFind the longest substring without repeats.
No. A sliding window on a string.
Check yourselfFind the kth largest number in an array.
No. A heap (or quickselect).
Check yourselfReverse a linked list.
No. Pointer rewiring on a linked list.
Problems in this pattern
- Topological sort · Medium · BFS on a DAG
- Connected groups (union-find) · Medium · Union-find
- Shortest paths (Dijkstra) · Medium · Weighted graph
- Course schedule (cycle check) · Medium · DFS states
Summary: say it in the interview
- Order and cycles: Topological sort or DFS states tell you whether tasks can be ordered, and expose loops.
- Groups and routes: Union-find answers "same group?" fast. Dijkstra finds cheapest paths when edge costs differ.