Graph Algorithms: BFS, DFS, Shortest Paths & Topological Sort

Q: When should I use BFS vs DFS?

Use BFS when you need the shortest path in an unweighted graph or want to explore in order of distance from the start (fewest steps, nearest first) — it uses a queue and visits level by level. Use DFS when you need to explore deeply: detecting cycles, checking connectivity, finding paths, or topological sorting — it uses recursion or a stack. Both are O(V + E); the choice is about the order you want to visit nodes and what the problem asks.

Q: What's the difference between an adjacency list and an adjacency matrix?

An adjacency list stores, for each node, a list of its neighbors — O(V + E) space, efficient for sparse graphs (the common case), but checking "is there an edge between A and B?" can take O(degree). An adjacency matrix is a V×V grid marking every possible edge — O(1) edge checks but O(V²) space regardless of how few edges exist. Use the list by default; use the matrix only for dense graphs or when constant-time edge queries dominate.

Graph Algorithms

A graph is a set of nodes (vertices) connected by edges — the most general way to model relationships. Roads between cities, friends in a social network, dependencies between tasks, links between web pages: all are graphs. Once you recognize a problem as a graph problem, a well-developed toolkit of algorithms applies, which is why graphs are one of the most important topics in computer science and interviews.

The two foundational traversals — breadth-first search (BFS) and depth-first search (DFS) — underlie most of the rest. Add shortest-path and ordering algorithms on top, and you can solve a remarkable range of real problems.

TL;DR

A graph is nodes + edges; it models relationships (maps, networks, dependencies).
BFS explores level by level (shortest path in unweighted graphs); DFS goes deep.
Dijkstra finds shortest paths in weighted graphs; topological sort orders dependencies.
Choose the representation (adjacency list vs matrix) by density.

Quick Example

Graphs are usually stored as an adjacency list — each node maps to its neighbors:

Representations

Adjacency list — each node stores a list of its neighbors. Space O(V + E); efficient for sparse graphs (most real-world graphs). The default choice.
Adjacency matrix — a V×V grid where cell [i][j] marks an edge. O(1) edge lookup but O(V²) space; good only for dense graphs or when you constantly query "is there an edge?"

Graphs can be directed (edges have direction) or undirected, and weighted (edges carry a cost) or unweighted.

Traversal: BFS & DFS

BFS uses a queue, explores level by level, and finds the shortest path in unweighted graphs. Great for "fewest steps" problems.
DFS uses recursion/a stack, dives deep first, and suits cycle detection, connectivity, and topological sorting.

Both are O(V + E).

Shortest Paths & Ordering

Dijkstra's algorithm — shortest paths from a source in a graph with non-negative weights, using a priority queue (heap). O((V + E) log V). The backbone of routing and maps.
Bellman-Ford — handles negative weights (and detects negative cycles), slower at O(V·E).
Topological sort — orders the nodes of a directed acyclic graph (DAG) so every edge points forward. Used for build systems, task scheduling, and dependency resolution.

What Graphs Model

Maps & routing — shortest/fastest path (Dijkstra, A*).
Social networks — connections, degrees of separation (BFS).
Dependencies — build order, task scheduling (topological sort).
Web & references — link graphs, PageRank.
Networks — flow, connectivity, spanning trees.

Best Practices

Use an adjacency list unless the graph is dense or you need O(1) edge checks.
BFS for unweighted shortest paths; Dijkstra for weighted.
Track visited nodes — graphs have cycles; unguarded traversal loops forever.
Topological sort for dependency ordering — and detect cycles (no valid order exists if one exists).
Watch DFS recursion depth — deep graphs can overflow the stack; use an explicit stack.

Common Mistakes

Forgetting to track visited nodes

Using BFS for weighted shortest paths

FAQ

When should I use BFS vs DFS?

Use BFS when you need the shortest path in an unweighted graph or want to explore in order of distance from the start (fewest steps, nearest first) — it uses a queue and visits level by level. Use DFS when you need to explore deeply: detecting cycles, checking connectivity, finding paths, or topological sorting — it uses recursion or a stack. Both are O(V + E); the choice is about the order you want to visit nodes and what the problem asks.

What's the difference between an adjacency list and an adjacency matrix?

An adjacency list stores, for each node, a list of its neighbors — O(V + E) space, efficient for sparse graphs (the common case), but checking "is there an edge between A and B?" can take O(degree). An adjacency matrix is a V×V grid marking every possible edge — O(1) edge checks but O(V²) space regardless of how few edges exist. Use the list by default; use the matrix only for dense graphs or when constant-time edge queries dominate.

Why can't I use Dijkstra's algorithm with negative edge weights?

Dijkstra assumes that once it finalizes the shortest distance to a node, that distance can't improve — which holds only when all weights are non-negative (you can never reach a node more cheaply by taking a longer detour). A negative edge can make a longer path cheaper, breaking that assumption and producing wrong results. For graphs with negative weights, use Bellman-Ford, which is slower (O(V·E)) but handles them and can detect negative cycles.

What is topological sorting used for?

Topological sort orders the nodes of a directed acyclic graph (DAG) so that every edge goes from earlier to later — i.e., every prerequisite comes before what depends on it. It's the algorithm behind build systems (compile dependencies first), task schedulers, course prerequisite ordering, and package dependency resolution. If the graph has a cycle, no valid ordering exists — which is exactly how these systems detect circular dependencies.