Graph Algorithms in Production: How BFS, DFS, and Dijkstra Actually Power the World

Graph algorithms feel like an academic hazing ritual to a lot of engineers: memorize the BFS and DFS boilerplate, pass the whiteboard, forget it by onboarding. This guide is for the candidate who wants the opposite - to understand why top companies keep asking these questions, because the same four algorithms (BFS, DFS, Dijkstra, and A*) are running in production at massive scale right now. Get the production framing and you stop sounding like a rote memorizer and start sounding like an engineer.

We'll cover how to represent a graph in memory, then walk each algorithm from the textbook definition to the real system it powers and the "senior" optimization an interviewer loves to hear.

Why interviewers care about graphs

Modern data is hyper-connected. Friends, web pages, road intersections, package dependencies, and microservices all form graphs. An interviewer asking you to traverse one is checking whether you can model a messy real-world relationship as nodes and edges and then reason about cost. That modeling step is the part most candidates skip, and it's the part that separates a passing answer from a strong one.

Graph representation: matrix vs. adjacency list

Before you run any algorithm, you have to store the graph. The representation you pick sets your space and time ceiling, so name it out loud in an interview.

• Adjacency matrix: a 2D array where matrix[i][j] = 1 when an edge connects node i and node j. It uses O(V^2) space (V = vertices). Great for dense graphs and O(1) edge lookups, wasteful for sparse ones.
• Adjacency list: a map (or array) where each node points to a list of its neighbors. It uses O(V + E) space (E = edges) and is the industry default for large, sparse production graphs.

Most real graphs are sparse. A social user has hundreds of friends, not billions, so the matrix would be almost entirely zeros. The list is the safe default to reach for.

Dimension	Adjacency matrix	Adjacency list
Space	O(V^2)	O(V + E)
Check if edge (u, v) exists	O(1)	O(degree(u))
Iterate a node's neighbors	O(V)	O(degree(u))
Best for	Dense graphs, frequent edge checks	Sparse graphs (most real systems)
Typical production use	Small/dense matrices, some ML adjacency	Social graphs, road networks, dependency graphs

Breadth-first search (BFS): the engine of social networks

BFS explores level by level, radiating outward from the source using a queue. That sweeping behavior makes it the optimal algorithm for the shortest path in an unweighted graph - every edge counts as one hop, so the first time you reach a node you've reached it by the fewest hops.

Production use case: "People You May Know"

Connection suggestions traverse a social graph. You are the source node; your direct friends are degree 1, their friends degree 2. Run BFS out to degree 2 or 3 and you surface people who share mutual connections without being directly linked to you. The same level-by-level structure also powers things like "reachable within N hops" features.

The senior optimization: bidirectional BFS

Running a plain BFS to find the shortest path between two users on a huge graph blows up memory as the frontier grows. The senior move is bidirectional BFS: launch one search from user A and another from user B simultaneously, and stop when the two frontiers meet. This cuts the explored space from roughly O(b^d) to O(b^(d/2)), an exponential reduction rather than a linear one.

Depth-first search (DFS): mapping dependencies

DFS plunges as deep as possible down one path before backtracking, using the call stack (or an explicit stack). It does not guarantee a shortest path, but its recursion is memory-efficient and it's the natural tool for structure and ordering problems.

Production use case: cycle detection and topological sort

In operating systems and databases, DFS detects cycles in dependency or wait-for graphs, which is how you find and break deadlocks.

DFS is also the heart of topological sorting. When you run a package install or compile a large codebase, the build system models dependencies as a Directed Acyclic Graph (DAG) and uses DFS to compute a valid execution order, so a library builds before the code that imports it. If a cycle exists, there's no valid order, which is exactly the error a build tool reports.

Dijkstra's algorithm: navigating the weighted world

BFS breaks down the moment edges cost different amounts. For a weighted graph - where edges carry distance, latency, or price - Dijkstra's algorithm uses a priority queue (min-heap) to always expand the currently cheapest known path. (Standard Dijkstra assumes non-negative weights; negative edges need a different algorithm such as Bellman-Ford.)

Video: Dijkstra's Algorithm explained (Computerphile)

Production use case: GPS routing and network paths

Routing a trip translates the physical world into a weighted graph: intersections are nodes, roads are edges weighted by length, speed limit, and live traffic. Network routing does the same with links weighted by latency or cost.

The senior optimization: A* search

Plain Dijkstra searches outward in every direction with no sense of where the goal is. A* search adds a heuristic - for maps, the straight-line distance to the destination - that biases exploration toward the goal, cutting the number of nodes evaluated. The trade-off worth naming in an interview: A* is only guaranteed to find the optimal path when its heuristic is admissible (never overestimates the true remaining cost).

Quick reference: which algorithm, when

Algorithm	Data structure	Finds	Use when
BFS	Queue	Shortest path by hop count	Graph is unweighted; you want fewest steps / nearest layers
DFS	Stack / recursion	A path, cycles, ordering	You need cycle detection, topological sort, or full traversal
Dijkstra	Min-heap (priority queue)	Shortest path by total weight	Edges have non-negative weights/costs
A*	Min-heap + heuristic	Shortest path, goal-directed	Weighted graph and you can estimate distance to the goal

How to talk about this in an interview

The code is the easy part. The signal an interviewer is listening for is whether you connect the algorithm to its constraints and a real system.

Do	Don't
State your representation and its space cost up front	Jump straight into code with no model
Name the data structure that makes it work (queue, stack, heap)	Hand-wave "we just search the graph"
Call out weighted vs. unweighted before choosing BFS or Dijkstra	Use BFS on a weighted graph and assume it's shortest
Mention an optimization (bidirectional BFS, A*) and its precondition	Claim an optimization without its caveat (admissible heuristic, non-negative weights)
Tie it to a production analogy (routing, dependencies, suggestions)	Treat it as pure trivia disconnected from real systems

Want to drill the patterns these algorithms show up in? For broader prep walkthroughs, browse the interview guides and the full resource library.

How to Use This Page as a Prep Plan

Do not treat this as passive reading. Convert the ideas in this page into a short weekly loop: learn one idea, practice it under interview conditions, then write down what changed. That is the fastest way to turn advice into visible interview behavior.

Prep area	What you need to prove	Practice artifact
Problem	Name the user, pain, and current workaround.	One crisp problem statement.
Success	Define primary and guardrail metrics.	Metric tree with instrumentation notes.
Solution	Compare options before choosing.	Tradeoff table with risks.
Execution	Plan rollout, learning, and rollback.	Experiment or launch checklist.

For Graph Algorithms in Production: How BFS, DFS, and Dijkstra Actually Power the World, the strongest candidates usually do three things well: they make their assumptions explicit, they use concrete examples instead of vague claims, and they review mistakes quickly enough that the next practice rep is better than the last one.

FAQ

When should I use BFS instead of Dijkstra?

Use BFS when the graph is unweighted (every edge is one hop) - it finds the fewest-hops shortest path in O(V + E) and is simpler. Switch to Dijkstra the moment edges carry different costs. Running BFS on a weighted graph will return a path with the fewest edges, not the cheapest, which is often wrong.

Why is an adjacency list usually preferred over a matrix?

Most real-world graphs are sparse: nodes connect to a small fraction of all other nodes. An adjacency list stores only the edges that exist (O(V + E)), while a matrix reserves space for every possible edge (O(V^2)), most of which are empty. The matrix is mainly worth it for dense graphs or when you need constant-time "does edge (u, v) exist" checks.

Is A* always better than Dijkstra?

No. A* is faster when you have a good, admissible heuristic (like straight-line distance on a map) because it steers the search toward the goal. Without a meaningful heuristic, A* degrades to Dijkstra, and a bad heuristic that overestimates can make A* return a non-optimal path. Dijkstra is the safe default when you can't estimate distance to the goal.

How does DFS detect a cycle?

During DFS you track which nodes are currently on the active recursion stack. If you reach a node that's already on that stack (a "back edge"), you've found a cycle. This is exactly how build tools and schedulers catch circular dependencies and how systems detect deadlocks in wait-for graphs.

Do I need to memorize the code, or understand the concepts?

Both, but understanding wins interviews. Memorized code falls apart the moment the interviewer changes a constraint (add weights, add a target, ask for all shortest paths). If you understand which data structure drives each algorithm and what assumption it relies on, you can adapt on the spot - which is the actual skill the question is screening for.