Graphs, BFS, and DFS

Graphs model relationships: social networks, road maps, the web, package dependencies, and game states are all nodes connected by edges. Two traversal algorithms unlock nearly everything you do with graphs: breadth-first search (BFS) explores level by level using a queue, and depth-first search (DFS) dives deep using a stack or recursion. If you know BFS, DFS, and a dictionary-based adjacency list, you can solve most graph problems you will ever meet.

What You'll Learn

• Representing graphs with adjacency lists (dicts of lists)
• BFS with a deque, and why it finds shortest paths
• DFS with recursion, and what it is best at
• Counting connected components, a bread-and-butter application

Representing a Graph

The standard Python representation is a dictionary mapping each node to a list of its neighbors:

For an undirected graph, every edge appears in both directions. A directed graph (like "follows" on social media) lists each edge once, from source to target.

BFS: Explore in Rings

BFS visits the start node, then all its neighbors, then all their neighbors, expanding outward like ripples. The queue (deque!) guarantees closer nodes are processed first, which makes BFS the algorithm for shortest paths in unweighted graphs:

Note the three moving parts, common to every BFS: a queue of nodes to process, a visited set (here the distances dict doubles as one), and a loop that pops, then pushes unvisited neighbors. Forget the visited check and a cycle loops forever.

DFS: Dive Deep, Then Backtrack

DFS follows one path as far as it goes, then backtracks. Recursion gives the cleanest implementation, because the call stack is the stack:

BFS or DFS? Both visit every reachable node in O(V + E). Choose by shape of question:

• Shortest/fewest steps: BFS
• Explore everything, detect cycles, topological order, backtracking puzzles: DFS

Application: Connected Components

"How many separate friend groups are there?" Run a traversal from every unvisited node; each launch discovers one component. This exact pattern counts islands in a grid, finds clusters, and checks network connectivity. Try it fullscreen:

Grids Are Graphs Too

A 2D grid is a graph where each cell connects to its up/down/left/right neighbors. The famous "number of islands" problem is connected components on a grid:

Exercises

Key Takeaways

• Represent graphs as dicts mapping node to neighbor list; grids are graphs too
• BFS uses a queue and finds shortest paths in unweighted graphs
• DFS uses recursion (or an explicit stack) and suits full exploration and backtracking
• Every traversal needs a visited set, or cycles will trap it forever
• Both run in O(V + E); the pattern "traverse from every unvisited node" counts components and islands