Same graph, two orders. BFS visits nearest-first with a queue; DFS plunges deep with a stack.
Graphs are the most general data structure there is — nodes connected by edges — and an enormous number of real problems are secretly graph problems. Social networks, dependency trees, road maps, knowledge graphs, the web itself: all graphs. Which means the two fundamental ways of walking a graph, breadth-first search (BFS) and depth-first search (DFS), are two of the most reusable tools you can own. And they’ve found a prominent new home in AI — GraphRAG, at its core, is a graph traversal. This is the refresher.
The two strategies
Both BFS and DFS visit every reachable node exactly once. The only difference is the order, and that difference comes down to one data-structure choice.
BFS uses a queue (first-in, first-out). It explores the graph in rings of increasing distance from the start: all the immediate neighbors first, then their neighbors, then the next layer out. In the diagram, starting from node 1, BFS visits 1, then both of 1’s children (2, 3), then their children (4, 5) — level by level. Because it fans out evenly, the first time BFS reaches a node, it has found the shortest path to it (in an unweighted graph). That property is what makes it the go-to for “fewest hops” questions.
DFS uses a stack (last-in, first-out) — often the call stack, via recursion. It plunges as deep as it can down one branch before backing up and trying the next. From node 1 it goes 1 → 2 → 3, hits a dead end, backtracks, tries 4, backtracks again, then explores 5 — one whole branch exhausted before moving to siblings. DFS naturally follows paths to their end, which makes it the right tool for questions about structure: is there a cycle? what’s a valid ordering?
That’s the entire distinction: queue vs stack, nearest-first vs deepest-first. Everything else follows.
Which one, when
- Reach for BFS when distance matters. Shortest path in an unweighted graph, “friends within 2 hops,” “nearest node that satisfies X,” level-order processing. (When edges have weights, BFS generalizes to Dijkstra’s algorithm — same fan-out idea, priority queue instead of a plain queue.)
- Reach for DFS when structure matters. Cycle detection, topological sort (ordering tasks so dependencies come first), finding connected components, exhaustive search of all paths, and anything naturally recursive like walking a tree.
Both run in O(V + E) — you touch every vertex and every edge once. They’re equally cheap; you choose by what you need, not by speed.
The one bug everyone hits: the visited set
Here is the mistake that bites everyone at least once. A graph can have cycles. If node A links to B, B links to C, and C links back to A, a naive traversal will loop A → B → C → A → B → C forever. The fix is mandatory and simple: keep a visited set, and never process a node you’ve already seen. On a tree (no cycles by definition) you can skip it; on a general graph you cannot. The bottom line of the diagram says it plainly — forget the visited set and your walk becomes an infinite loop. This is the same “guarantee termination” discipline as a recursion’s base case, and forgetting it is the number-one graph-traversal bug in production.
Where traversal is quietly running
- Dependency resolution. Package managers (npm, pip, apt), build systems, and module loaders topologically sort a dependency graph via DFS. The dreaded “circular dependency” error is literally DFS detecting a cycle.
- Networks and infrastructure. Shortest-path routing, service dependency mapping, blast-radius analysis (“what breaks if this node fails?”) are BFS/DFS over the topology.
- The web. A crawler doing BFS from a seed URL, with a visited set to avoid re-crawling — and, as we saw, often a Bloom filter to hold that visited set at web scale.
- Garbage collection. The reachability trace from the GC post is a graph traversal from the roots. Live objects are the ones the walk reaches.
The AI-era relevance: GraphRAG is a traversal
This is where a classic algorithm becomes a headline AI technique.
Knowledge graphs and GraphRAG. Standard RAG retrieves chunks by vector similarity — great for “find me text about X,” weak at “how are X and Y connected?” GraphRAG builds a knowledge graph of entities and relationships, and answering a question becomes traversing that graph: start at the entities in the query, walk out along relationships to gather connected context, and feed that neighborhood to the model. That walk is BFS/DFS. “Give me everything within 2 hops of this entity” is a bounded BFS; “trace the chain of dependencies from this service” is a DFS. The reason graph databases (Neo4j and friends) pair so naturally with LLMs is that they make these traversals fast and expressive, turning multi-hop reasoning into a query instead of a prompt-engineering hope.
Agent planning and tool graphs. An agent exploring possible action sequences is searching a graph of states, and whether it explores broadly (BFS-like, considering many options shallowly) or deeply (DFS-like, committing to a plan and following it) is a real design choice with real cost and latency consequences. The same bounded-depth discipline that keeps a recursion safe keeps that search from exploding.
Dependency and lineage graphs for data/ML pipelines. Data lineage, feature dependencies, and model-artifact provenance are all graphs you traverse to answer “what does this depend on?” and “what’s affected if this changes?” — increasingly important for auditability in regulated AI systems.
The takeaway
BFS and DFS are the same walk with a different container — a queue for nearest-first, a stack for deepest-first — and that one choice determines whether you’re finding shortest paths or analyzing structure. Both are cheap, both need a visited set to survive cycles, and both turn out to underpin an astonishing range of systems, from your package manager to the newest GraphRAG pipeline. When a problem involves things connected to other things, you’re looking at a graph, and these two traversals are how you explore it. GraphRAG didn’t invent a new idea; it gave a very old walk a very good new job.