Graph Algorithms: BFS and DFS Explained

1What Are BFS And DFS

Breadth-first search and depth-first search are the two foundational algorithms for systematically visiting every node in a graph. BFS explores outward in layers, visiting all neighbors of a node before moving on to their neighbors, while DFS plunges as deep as it can down one path before backtracking to try another. Both guarantee that every reachable node is visited exactly once when implemented with a visited set.

A graph is simply a collection of nodes, called vertices, connected by edges. Graphs model everything from social networks and road maps to dependency chains and web links. Traversal is the act of walking through these connections in a defined order, and BFS and DFS are the two canonical strategies for doing so.

The difference between them comes down to the order in which nodes are explored, which in turn is determined by the data structure each uses to track what to visit next. That single choice, a queue versus a stack, produces two algorithms with strikingly different behaviors and use cases.

Both algorithms are worth learning together precisely because they are so similar in structure yet so different in effect. Once you have written one, you have almost written the other, and comparing them side by side is one of the clearest ways to understand how a data structure shapes an algorithm. That insight, that the container you choose determines the behavior you get, is a lesson that recurs throughout computer science.

2How Graphs Are Represented

Before traversing a graph you need to store it. The two common representations are the adjacency list and the adjacency matrix. An adjacency list keeps, for each vertex, a list of the vertices it connects to. It is compact for sparse graphs where most possible edges do not exist, which describes most real-world graphs.

An adjacency matrix uses a grid where the cell at row i and column j indicates whether an edge exists between vertex i and vertex j. It offers constant-time edge lookups but uses space proportional to the square of the number of vertices, making it wasteful for large sparse graphs. For most traversal work the adjacency list is the practical default.

Graphs also come in flavors that affect traversal. A directed graph has edges that point one way, so you can travel from one vertex to another but not necessarily back. An undirected graph has edges that go both ways. Edges may also carry weights representing distance or cost. BFS and DFS as described here work on unweighted graphs, and recognizing which kind of graph you have is the first step before choosing an algorithm.

3How Breadth-First Search Works

BFS uses a queue, a first-in first-out structure. You start by placing the source node in the queue and marking it visited. Then you repeatedly remove the front node, examine each of its unvisited neighbors, mark them visited, and add them to the back of the queue. Because the queue preserves arrival order, you always process nearer nodes before farther ones.

This layered expansion is the defining trait of BFS. All nodes at distance one from the source are visited before any node at distance two, and so on. That property is exactly what makes BFS the natural choice for finding the shortest number of steps between two nodes in an unweighted graph.

Marking nodes as visited when you enqueue them, not when you dequeue them, is important. It prevents the same node from being added to the queue multiple times, which would waste work and could distort the level structure. This small discipline keeps BFS both correct and efficient.

4How Depth-First Search Works

DFS uses a stack, a last-in first-out structure, though it is often written recursively so the call stack plays that role implicitly. Starting from the source, you visit a node, mark it, and then recurse into one of its unvisited neighbors, going as deep as possible before backtracking. When a node has no unvisited neighbors left, you return to the previous node and try its next option.

This deep-diving behavior means DFS may reach a faraway node long before it finishes exploring nodes close to the source. It fully explores one branch of the graph before moving to the next. That makes DFS well suited to problems about paths, connectivity, and structure rather than shortest distances.

You can write DFS recursively for clean, readable code, or iteratively with an explicit stack when you want to avoid deep recursion. Both produce the same traversal order family, though the exact sequence can differ slightly depending on how you push neighbors onto the stack.

5Why Tracking Visited Nodes Matters

Graphs frequently contain cycles, where following edges can lead you back to a node you have already seen. Without a mechanism to remember which nodes you have visited, both BFS and DFS would loop forever, endlessly revisiting the same nodes. A visited set, often a boolean array or a hash set, solves this.

Every time you first encounter a node you mark it visited, and you never process a node that is already marked. This guarantees each node is handled once and gives both algorithms their linear running time. Forgetting this step is one of the most common beginner mistakes and leads to infinite loops or stack overflows.

6Time And Space Complexity

Both BFS and DFS visit each vertex once and examine each edge once, giving a running time of O(V plus E), where V is the number of vertices and E is the number of edges. This linear complexity is optimal because any complete traversal must at least look at every node and connection.

Space usage differs in character. BFS may hold an entire level of the graph in its queue, which for wide graphs can be substantial. DFS uses space proportional to the longest path it is currently exploring, either in the explicit stack or the recursion depth. For very deep graphs DFS can consume significant stack space, while for very wide graphs BFS can consume significant queue space.

7BFS And Shortest Paths

The headline application of BFS is finding the shortest path in an unweighted graph. Because BFS expands in order of increasing distance, the first time it reaches a target node it has done so by the fewest possible edges. By recording each node's parent as you enqueue it, you can reconstruct the actual shortest path afterward, not just its length.

This makes BFS the go-to for problems like the minimum number of moves in a puzzle, the fewest connections between two people in a network, or the shortest route on a grid where every step costs the same. When edges carry different weights, however, plain BFS no longer suffices and you need a weighted algorithm instead.

Grids are a common place BFS appears in disguise. A maze or a game board can be treated as a graph where each cell is a vertex connected to its neighbors. Running BFS from a starting cell finds the fewest steps to any reachable cell, which solves shortest-path puzzles cleanly. Seeing a grid as an implicit graph is a mental shift that unlocks a whole category of problems.

8Where DFS Shines

DFS excels at problems about structure. It naturally detects cycles, because encountering an already-in-progress node during a deep dive reveals a loop. It finds connected components by launching a fresh traversal from each unvisited node and grouping everything reachable. It also underlies topological sorting, which orders tasks so that every dependency comes before the task that needs it.

DFS is also the backbone of backtracking algorithms, where you explore choices deeply and undo them when they lead to dead ends. Maze solving, generating permutations, and constraint puzzles all lean on the depth-first pattern. When a problem is about exploring all possibilities or understanding how a graph is put together, DFS is usually the right instinct.

9Choosing Between BFS And DFS

The choice hinges on what you need. If you want the shortest path or the closest node in an unweighted graph, reach for BFS. If you need to explore all paths, detect cycles, order dependencies, or examine structure, DFS is typically cleaner and more natural. Neither is universally better; they are complementary tools.

Memory can also guide the decision. On a very wide, shallow graph, DFS may use far less memory than BFS. On a very deep, narrow graph, BFS may avoid the deep recursion that troubles DFS. Considering the shape of your particular graph alongside the problem you are solving leads to the right pick.

10Common Mistakes To Avoid

Beyond forgetting the visited set, a frequent error is marking BFS nodes as visited at the wrong time, which lets duplicates into the queue. Another is assuming BFS gives shortest paths on weighted graphs, which it does not. And in DFS, writing recursion without a base case or without checking visited status leads straight to infinite loops.

Handling disconnected graphs is another subtlety. A single traversal only reaches nodes connected to the starting point. If the graph has multiple separate components, you must restart the traversal from each unvisited node to cover them all. Remembering this prevents silently missing entire parts of the graph.

11What Comes After BFS And DFS

BFS and DFS are the entry point to a rich family of graph algorithms. When edges carry weights, Dijkstra's algorithm generalizes the shortest-path idea by always expanding the closest unfinished node using a priority queue rather than a plain queue. It answers the weighted version of the question BFS answers for unweighted graphs.

Other algorithms build on traversal too. Topological sort orders the vertices of a directed acyclic graph so dependencies come first, and it is often implemented with DFS. Algorithms for finding minimum spanning trees connect all vertices at least cost. Every one of these assumes you are already comfortable walking a graph, so the effort you invest in BFS and DFS pays dividends across everything that follows.

The point is not to learn all of these at once but to see BFS and DFS as the foundation. Once traversal feels automatic, the more advanced algorithms read as variations on a theme rather than entirely new ideas, which makes them far less intimidating to pick up.

12Practice And Next Steps

Graph traversal is a prerequisite for a huge range of more advanced algorithms, including weighted shortest paths, minimum spanning trees, and network flow. Getting comfortable with BFS and DFS now builds the foundation everything else stands on. The best way to learn is to implement both from scratch and trace them by hand on small graphs.

On SkillVeris you can practice traversals on interactive graphs, watch the queue and stack evolve step by step, and solve challenges that make the difference between BFS and DFS concrete. Build both algorithms yourself, apply them to shortest-path and cycle-detection problems, and you will be ready for the graph algorithms that build on them.

Start with small graphs you can draw, predict the visit order before running your code, and check whether your prediction matches. That habit of predicting then verifying is how traversal moves from something you follow step by step to something you understand at a glance, ready to apply the moment a problem reveals its hidden graph.