Graph Data Structures: BFS vs DFS Explained

A graph is a data structure made of nodes (also called vertices) and the edges connecting them — a general-purpose model for anything that looks like a network: friendships in a social app, roads between cities, dependencies between packages, links between web pages. Breadth-first search (BFS) and depth-first search (DFS) are the two fundamental ways to visit every reachable node in a graph, and the order in which they visit nodes makes each suited to different problems.

Graphs, briefly

A graph consists of vertices and the edges between them. Edges can be directed (a one-way relationship, like “page A links to page B”) or undirected (a symmetric relationship, like “these two users are friends”), and they can be weighted (an edge carries a cost or distance) or unweighted. A tree is actually a special case of a graph — one with no cycles and exactly one path between any two nodes — but general graphs allow cycles and multiple paths, which is what makes traversal order matter.

Graphs are typically represented one of two ways: an adjacency list, where each node keeps a list of its neighbors (compact, and the common choice for sparse graphs), or an adjacency matrix, a grid where cell [i][j] indicates whether an edge connects node i and node j (simpler to reason about, but wasteful for large sparse graphs since most cells are empty).

Breadth-first search: layer by layer

BFS starts at a chosen node and explores outward one layer at a time — it visits every neighbor of the starting node before moving on to any of their neighbors. It uses a queue: add the start node, then repeatedly dequeue a node, visit it, and enqueue any of its unvisited neighbors.

Because a queue is first-in-first-out, nodes get visited in the exact order they were discovered — which means BFS explores the graph in expanding rings around the starting point, one edge-distance at a time.

    A
   / \
  B   C
 /     \
D       E

Starting from A, BFS visits A, then B and C (both one edge away), then D and E (both two edges away) — strictly by distance from the start.

BFS is the right tool when:

• You need the shortest path between two nodes in an unweighted graph — because BFS visits nodes in increasing order of distance, the first time it reaches the target node, that’s guaranteed to be via a shortest path.
• You’re searching level by level, such as finding everyone within two connections of a person in a social graph.

Depth-first search: as far as possible, then backtrack

DFS starts at a chosen node and follows one path as far as it can go before backtracking — it commits to a neighbor, then commits to that node’s neighbor, and keeps going deep until it hits a dead end, then backs up to the most recent branching point and tries a different direction. It uses a stack — either an explicit one, or recursion, which uses the call stack implicitly.

Using the same graph, DFS starting from A might visit A, B, D (going as deep as possible down the left branch), then backtrack to A and visit C, E.

DFS is the right tool when:

• You need to detect cycles in a graph, since a DFS that revisits a node still on the current path (not yet fully backtracked) has found a cycle.
• You’re doing a topological sort — ordering nodes so every directed edge points from an earlier node to a later one, which is exactly how tools resolve build dependencies or package installation order.
• You need to explore every possible path, such as in maze-solving or exhaustive search problems, since DFS naturally follows one path to its end before trying alternatives.
• Memory is a concern relative to graph width: DFS’s stack only needs to hold one path’s worth of nodes at a time, whereas BFS’s queue can hold an entire layer, which may be much larger in a wide graph.

BFS vs DFS

	BFS	DFS
Data structure used	Queue	Stack (or recursion)
Traversal order	Layer by layer, by distance from start	As deep as possible, then backtrack
Finds shortest path (unweighted)	Yes	No
Good for cycle detection	Possible, less natural	Yes, natural fit
Good for topological sort	No	Yes
Memory use on wide graphs	Can be high (holds a full layer)	Typically lower (holds one path)
Memory use on deep graphs	Typically lower	Can be high (deep recursion or stack)

Marking visited nodes

Both algorithms need to track which nodes have already been visited — without that, a graph containing a cycle would send either algorithm looping forever, since it would keep re-discovering the same nodes through the cycle. This is normally done with a set or a boolean flag per node, checked before a node is enqueued (BFS) or recursed into (DFS), and it’s usually the detail that trips people up when implementing either algorithm from scratch.

Beyond plain traversal

BFS and DFS are the foundation that more specialized graph algorithms build on. Dijkstra’s algorithm, for finding shortest paths in a weighted graph, is essentially BFS with a priority queue replacing the plain queue, so it always expands the currently-cheapest node next rather than strictly by edge-count. Understanding plain BFS and DFS first makes these variants far more approachable, since the added complexity is usually a single change to the underlying data structure, not a different algorithm altogether.

Both algorithms run in time proportional to the number of vertices plus edges — see Big O notation for how that kind of complexity is expressed and compared to less efficient alternatives, like a naive approach that reprocesses a graph from scratch for every query rather than traversing it once.

The takeaway

Graphs generalize trees, linked lists, and other connected structures into nodes and edges, and BFS and DFS are the two ways to systematically visit every reachable node. BFS’s queue-based, layer-by-layer order makes it the natural choice for shortest-path problems on unweighted graphs; DFS’s stack-based, go-deep-then-backtrack order makes it the natural fit for cycle detection and topological sorting. Most graph problems reduce to choosing the right one of these two and adapting it slightly — knowing both well covers a large share of graph algorithms you’ll actually encounter.