Depth-First Search (DFS) and Breadth-First Search (BFS) are among the most widely used graph search techniques. You might already be familiar with their basic ideas and have used them frequently. However, gaining a deeper understanding of these algorithms is essential, as they form the foundation of many advanced techniques and real-world applications.

In this article, we offer a comprehensive and systematic introduction to DFS and BFS. We’ll begin by exploring the core concept of graph search and then study both algorithms from that perspective. We’ll also look at more advanced search techniques that build on DFS and BFS, along with practical use cases that highlight their differences and strengths. By the end of this article, you’ll have a solid grasp of how these fundamental algorithms work and where to apply them effectively.

Understanding Graph Search Algorithms

BFS and DFS are both graph search algorithms. Sometimes, you might use them without explicitly defining a graph—such as when solving an 8-puzzle game. However, there is still an underlying graph structure: the set of possible states forms the nodes, and the transitions between states act as edges. That’s essentially how these algorithms operate. So, before we dive deeper, let’s take a closer look at the core concept: graphs.

What Is a Graph?

A graph is a mathematical structure used to model relationships between objects. It consists of a set of nodes (or vertices) and edges that connect pairs of nodes. Graphs can be directed, where edges have a direction, or undirected, where they don’t. The graph model can be more complicated as

Although graphs are often implemented using data structures like adjacency lists or matrices in code, the concept itself is more abstract. In many problems—like puzzle solving, routing, or state space exploration—the graph isn’t always explicitly built, but it’s still there behind the scenes. Nodes represent states, and edges represent possible transitions between them.

Evaluation functions in graph search

Graph search refers to algorithms that systematically explore or traverse a graph. Typically, you start from a source vertex and expand outward by following its edges to discover new vertices. At each step, you need to choose which vertex to expand next. But how do you make that choice?

The decision is guided by an evaluation function, a key concept in graph search algorithms. This function is often defined as:

\[f(n) = g(n) + h(n)\]

Here, \(g(n)\) represents the cost from the start node to the current node \(n\) (also called the path cost), and \(h(n)\) is a heuristic estimate of the cost from \(n\) to the goal (known as the heuristic function). The total, \(f(n)\), gives the estimated cost of a path through \(n\), and is used to prioritize which vertex to explore next.

‍

Implementing the selection of the vertex with the minimum (or maximum) evaluation is not always straightforward. If you scan all candidate vertices each time, it can be expensive—specifically, with time complexity proportional to the size of the candidate set, which isn’t efficient in sparse graphs. To address this, we usually use priority queues to manage the candidate vertices. This data structure allows for efficient retrieval of the vertex with the best evaluation, as well as quick insertion of new ones.

However, for DFS and BFS, the evaluation functions are simple enough that we can use basic data structures instead: a stack for DFS and a queue for BFS. This simplicity is one of the reasons these two algorithms are so widely used and easy to implement.

This evaluation-function framework can help you understand many search algorithms, including DFS, BFS, Dijkstra’s algorithm, and A* as you read this graph search algorithm article.

What are DFS and BFS

In this section, we’ll explore the fundamentals of DFS and BFS through the lens of graph search algorithms.

DFS

Depth-First Search (DFS) is a graph search algorithm that uses the following evaluation function:

\[g(n)=\text{depth}(n),h(n)=0\]

Here, \(\text{depth}(n)\) refers to the node’s depth in the search tree. Since the evaluation only depends on depth, DFS always explores the deepest unvisited node first. In other words, nodes inserted most recently (i.e., deeper nodes) are prioritized. This behavior naturally forms a LIFO (Last In, First Out) structure—also known as a stack—which is why the algorithm is called Depth-First Search.

Non-recursive DFS implementation

Now we provide a Python example that manages the stack explicitly. In this code, we focus on demonstrating the use of a stack, rather than optimizing for efficiency in checking whether a node has been visited or selecting the next unvisited edge.

def dfs_iterative(graph, start):
    # Non-recursive DFS where stack maintains current path from root
    visited = set()
    stack = []
    stack.append(start)  # Stack represents current path from root
    
    while stack:
        node = stack.pop()  # Pop current node
        
        if node not in visited:
            visited.add(node)
            print(node)  # Process node
            
            stack.append(node)  # Push back to maintain path
            
            # Find first unvisited neighbor
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    stack.append(neighbor)  # Push to extend path
                    break
            else:
                # No unvisited neighbors, remove current node (backtrack)
                stack.pop()
        # If already visited, node is already popped (backtrack)

Recursive DFS implementation

In practice, DFS is often written recursively. In this case, we rely on the system’s call stack (handled by the language runtime or operating system) instead of managing our own.

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()

    if node not in visited:
        visited.add(node)
        print(node)  # Process the node

        for neighbor in graph[node]:
            dfs_recursive(graph, neighbor, visited)

Both versions achieve the same goal—exploring as deep as possible before backtracking—but the recursive version is typically shorter and easier to read.

BFS

Breadth-First Search (BFS) is another fundamental graph search algorithm. It uses the same evaluation function as DFS:

\[g(n)=\text{depth}(n),h(n)=0\]

However, in BFS, nodes with smaller values of evaluation function (i.e., shallower depth) are given higher priority. That means nodes inserted earliest (i.e., closer to the root) are processed first. This leads to a FIFO (First In, First Out) traversal order, which naturally maps to a queue data structure.

BFS Implementation

Here is a Python example that uses a queue to perform BFS. As with the DFS example, the focus is on showing the algorithmic structure rather than optimizing performance. 

def bfs(graph, start):
    visited = set()
    queue = [start]

    while queue:
        node = queue.pop(0)  # Dequeue from the front
        if node not in visited:
            visited.add(node)
            print(node)  # Process the node

            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    queue.append(neighbor)  # Enqueue to the back

In BFS, nodes are explored level by level, which makes it particularly useful for finding the shortest path (in terms of number of edges) from the start node to any other node in an unweighted graph. The use of a queue ensures that nodes are expanded in the order they were discovered.

Key Use Cases of DFS and BFS

DFS and BFS may seem simple, but they serve as the foundation for many important algorithms and practical applications. Understanding when and why to use each one can help you choose the right approach for different problem types.

When to use DFS

DFS is arguably the most widely used graph search technique. It offers several key advantages:

• Low memory usage: DFS typically requires little memory, as the stack only needs to store the current path from the root to the current node.
  
  
• Simple and elegant code: The recursive version of DFS is compact, clean, and easy to write.
  
  
• Intuitive behavior: DFS feels natural—you can think of it as “walking” through the graph, diving deeper before backtracking.
  

In many problems, the specific search strategy doesn’t matter much—as long as the algorithm explores all valid options. In such cases, we often default to recursive DFS because it’s easy to implement and memory-efficient in practice. Examples include N-Queens, Sudoku, flood fill algorithm. Both DFS and BFS work for these problems if memory allows, but DFS is usually preferred for its simplicity.

Some problems align closely with the “depth-first” intuition, such as simulating a moving object traversing every edge. For example:

• Finding Eulerian circuits
• Approximating Hamiltonian circuits using DFS over a minimum spanning tree
  

DFS is also essential in connectivity-based algorithms, where BFS may not apply directly. These include:

• Cycle detection: Check whether the current edge points to a node already in the stack.
  
  
• Strongly connected components (SCCs): Algorithms like Tarjan’s and Kosaraju’s rely on DFS traversal and its associated tree structure.
  
  
• Biconnected components: Also depend on the structure of the DFS tree and low-link values.
  

When to Use BFS

The main strength of BFS is in finding the shortest path in unweighted graphs. In fact, you can think of BFS as a simplified version of Dijkstra’s algorithm when all edge weights are equal.

BFS is also ideal when you want to search layer by layer, such as:

• Finding all nodes at a specific distance from a source
  
  
• Checking whether a graph is bipartite
  
  
• Performing level-order traversal in a tree
  
  

Another notable advantage of BFS is that it’s easier to parallelize. Since each layer is independent, the expansion of nodes to the next layer can be distributed across multiple processors. This can significantly reduce search time in large graphs. See the Wikipedia page for more details.

More searching techniques based on DFS and BFS

DFS and BFS are foundational search algorithms, but in practice, they often serve as the building blocks for more advanced techniques. In this section, we’ll introduce a few common strategies that enhance or extend DFS and BFS: Iterative Deepening DFS (IDDFS), Bidirectional BFS, and Pruning.

Iterative Deepening DFS (IDDFS)

IDDFS combines the space efficiency of DFS with the completeness of BFS. It repeatedly runs DFS with increasing depth limits until the goal is found. At each iteration, DFS only explores nodes up to a specified depth.

Because it restarts DFS each time, IDDFS might seem inefficient. However, in practice, most of the work is done during the final iteration—the one that actually finds the goal. We won’t go into detailed analysis here, but intuitively, the number of nodes at each depth level forms a geometric sequence, so the total cost is dominated by the final iteration.

This technique is especially useful when the depth of the solution is unknown but expected to be relatively shallow, and the branching factor is large. Note that with BFS, the entire frontier must be stored in memory, which can quickly exceed capacity. In contrast, IDDFS uses a shallow stack that only tracks the current path from the root, keeping memory usage low.

IDDFS is commonly used in problems like puzzles and games, where the search space is large but the solution is expected to be near the starting point.

Bidirectional BFS

Bidirectional BFS is a powerful optimization when you know both the start and the goal nodes. Instead of searching from the start all the way to the goal, it performs two simultaneous BFS traversals: one forward from the start, and one backward from the goal. The search stops when the two frontiers meet.

This approach dramatically reduces the search space. While regular BFS has time and space complexity proportional to O(bd ) (where b is the branching factor and d is the depth of the solution), bidirectional BFS reduces this to O(bd/2), assuming symmetric branching.

It’s commonly used in shortest path problems on unweighted graphs. For example, in the 8-puzzle problem, where both the starting state and the goal state are known, you can apply bidirectional BFS by searching forward from the start and backward from the goal simultaneously.

Pruning

Pruning is a general strategy for reducing the search space by cutting off paths that are clearly unproductive. If you can determine that a certain path cannot lead to a valid or optimal solution, there’s no need to explore it further.

This typically involves checking constraints or conditions before expanding a node or continuing a path. For example, in puzzle-solving or optimization problems, you might prune paths that lead to invalid states, exceed cost limits, or duplicate previous work.

Pruning helps both DFS and BFS avoid unnecessary computation and can significantly improve performance, especially in large or exponential search spaces. It’s widely used in problems like constraint satisfaction, bounded pathfinding, and game tree search. The key is to prune safely—eliminating only paths that are guaranteed not to affect the final result.

For example, in a Sudoku solver, the algorithm typically fills in empty cells one by one using backtracking (a form of DFS). Without pruning, it might try all digits (1–9) in every empty cell, even if some clearly violate Sudoku rules.

With pruning, before placing a digit in a cell, the algorithm checks whether that digit already appears in the same row, column, or 3×3 box. If it does, the option is immediately discarded.

This simple pruning step prevents invalid paths from being explored and dramatically reduces the number of recursive calls needed to find a solution.

How Graph Traversal Works in Graph Databases and Engines

Traversal in graph databases and graph query engines is fundamentally path-oriented rather than node-oriented. In traditional graph algorithms such as depth-first search and breadth-first search, the goal is typically to visit all reachable nodes, often exactly once. In contrast, graph query languages such as Cypher and Gremlin, which are used in graph databases and query engines, are designed to find all paths that match a given pattern or traversal logic.

Rather than specifying how to traverse the graph step by step, you describe the structure or sequence of steps for the paths you want to explore. The engine then handles the traversal based on that description. In this path-based approach, the same node may appear multiple times across different paths. Unless explicitly constrained, traversal can revisit nodes repeatedly. The focus is not on visiting every node once, but on identifying all valid path structures that satisfy the query.

Traversal in Cypher and Gremlin

In Cypher, you can express a variable-length path using:

MATCH (a)-[*1..3]->(b)
RETURN a, b

This finds all paths of length one to three from node a to node b. The underlying engine typically uses a breadth-first traversal to prioritize shorter paths first. You are not explicitly specifying the use of breadth-first search; instead, you describe what you want to find, and the engine decides how to execute the traversal.

In Gremlin, a similar query might look like:

g.V(a).repeat(out()).times(3).emit()

This performs a three-step traversal outward from vertex a, emitting all intermediate and final results. Once again, you do not control the traversal strategy directly. Gremlin abstracts that away as part of its execution engine.

Parallelism in Distributed Graph Engines

When working with large-scale graphs in distributed environments, parallel execution becomes essential for performance. In path-based traversals that search for all matching paths, parallelism arises naturally because different paths can be explored independently. This allows traversal workloads to be spread across multiple machines, significantly improving scalability.

Although query writers do not manage parallelism directly, modern graph databases and engines optimize traversal execution under the hood to fully utilize available compute resources. This makes it possible to handle expressive graph queries at scale, even when exploring millions of paths.

To support efficient distributed traversal, systems rely on several key strategies. One of the most important is graph partitioning, where the graph is divided into subgraphs and distributed across machines. A well-designed partitioning scheme groups closely connected nodes together to minimize cross-machine communication during traversal. Another common strategy is replication, where frequently accessed or high-degree nodes are stored on multiple machines. This reduces access latency and prevents bottlenecks when many paths pass through the same node.

Conclusion

Depth-First Search (DFS) and Breadth-First Search (BFS) are fundamental graph traversal algorithms. DFS explores deeply along branches using a stack, ideal for path discovery, topological sorting, and memory-constrained situations in wide graphs. BFS explores level by level using a queue, guaranteeing the shortest path in unweighted graphs and excelling when goals are near the starting point.

These core methods form the basis for advanced techniques like Iterative Deepening DFS (IDDFS), Bidirectional BFS, and pruning, which enhance search efficiency. While graph query languages like Cypher and Gremlin abstract direct traversal choices, their engines often utilize BFS-like strategies for path-oriented queries, especially in parallel processing.

Ultimately, selecting the right algorithm—whether depth-first search, breadth-first search, or one of their derivatives—depends on the graph’s structure, the location of the goal, performance requirements, and available computing resources. A solid grasp of these algorithms is crucial for effective problem-solving in diverse applications.

Want to experiment with graph traversal yourself? Download our forever free Developer Edition or book a demo to see PuppyGraph in action.