BFS vs. DFS: Two Ways to Walk a Graph

Given a graph — dots connected by lines, as covered in this site's "what a graph actually is" — there's more than one reasonable order to visit every node, and the two standard approaches, breadth-first search (BFS) and depth-first search (DFS), visit that same graph in genuinely different orders, each useful for different questions.

BFS spreads outward like a ripple on a pond: start at one node, visit every node directly connected to it first, then every node connected to those, expanding outward one full ring at a time before going any deeper. It never rushes ahead down one path while ignoring the others — it fans out evenly, level by level.

DFS is the opposite instinct: like exploring a maze by picking a direction and following that single hallway as far as it goes, only backtracking to try a different branch once the current path dead-ends. It commits fully to one path before ever considering an alternative, which is a completely different visiting order from BFS's even, expanding ripple, even though both end up visiting every reachable node eventually.

The order each one visits nodes in isn't just a stylistic difference — it decides which one actually answers a given question. BFS is the right tool whenever "shortest" matters in terms of number of connections, like finding the fewest number of introductions between two people in a social network, because BFS guarantees it reaches every node in the fewest possible steps before moving further out. DFS is the right tool for questions like "does a path exist at all between these two nodes" or "is there a cycle in this graph," where you don't care which path you find, just whether one exists — committing fully to one path and backtracking as needed gets there without the bookkeeping BFS needs to expand evenly.

A concrete walkthrough makes the difference visible: starting from node A on a small graph where A connects to B and C, B connects to D, and C connects to D.