What Are BFS and DFS Algorithms, and When Should You Choose Each?
BFS and DFS are graph traversal algorithms that systematically find vertices reachable from a starting vertex. BFS expands level by level from nearby vertices, making it suitable when you need a path with the minimum number of edges in an unweighted graph. DFS follows one branch as far as possible before backtracking, so it is used as a foundation for problems such as structural analysis, cycle detection, and topological sorting. Neither is always better; the choice depends on the path criterion and the purpose of the graph. ocw.mit.edualgs4.cs.princeton.edu
What Do BFS and DFS Find in Graph Traversal?
A graph is a relational structure made up of vertices and edges. Vertices represent entities such as people, cities, web pages, or tasks, while edges represent connections between them, such as friendships, roads, links, or prerequisite relationships. The vertex set is denoted by , and the edge set by .
If edges have no direction, the graph is undirected. For example, a mutual friendship can usually be viewed as bidirectional. In contrast, relationships such as A following B or task A needing to finish before task B form a directed graph. In a directed graph, you can travel only in the direction of an arrow; you cannot automatically move in the opposite direction. ocw.mit.edu
The most basic question in graph traversal is, “Which vertices can be reached from a starting point ?” While answering this question, BFS and DFS can also record additional information, such as whether a vertex has been visited, the path by which each vertex was first reached, and the traversal order. However, a traversal starting from one vertex processes only the portion that is actually reachable from that vertex. It does not necessarily visit every vertex in the graph. ocw.mit.edu
A tree is also a type of graph. Therefore, BFS and DFS can be used for problems that look like trees, such as folder hierarchies or organizational charts. However, it is important to remember that a general graph can contain cycles that return to a vertex and multiple paths to the same vertex. Applying an implementation designed only for tree traversal directly to a general graph can cause duplicate visits.
How Does BFS Explore Nearby Vertices First?
BFS stands for Breadth-First Search. It first finds vertices reachable from the starting point by one edge, then vertices requiring two edges, then three edges, expanding the search range in that order. Here, distance is not physical distance or cost; it is the number of edges that must be traversed from the starting point. algs4.cs.princeton.edu
BFS usually uses a queue for this purpose. A queue is a FIFO (First In, First Out) data structure, meaning that the first item added is the first item removed. Put the starting vertex into the queue and mark it visited, then remove one vertex from the front of the queue. Mark all of that vertex's undiscovered neighbors as visited and add them to the back of the queue. Repeat this until the queue is empty. Because previously discovered nearby vertices are processed first, the level-by-level expansion is preserved. gh.cp-algorithms.comalgs4.cs.princeton.edu
For example, suppose that starting from A, you discover A's neighbors B and C. When BFS processes B, it discovers B's neighbors; it then processes C and discovers C's neighbors. Even if a vertex discovered from B is deeper, C, which was already placed in the queue at the same level, is processed first or in close sequence. The exact order between B and C can vary depending on the order in which adjacent vertices are stored.
The key to BFS is to mark a vertex visited as soon as it is discovered. If you delay marking it until it is removed from the queue, two vertices may each discover the same neighbor and insert it into the queue more than once. In a typical BFS, marking a new neighbor as discovered at the very moment it is added to the queue is simpler and safer.
Under What Conditions Does BFS Provide a Shortest Path?
BFS is often chosen because, in an unweighted graph, it finds a path with the minimum number of edges from the starting vertex to every reachable vertex. It examines all vertices one step away from the start before examining vertices two steps away, so a path with fewer edges than the path that first discovers a vertex cannot appear later. If you record the preceding vertex as the parent when each vertex is first discovered during BFS, those parent pointers form a shortest-path tree. algs4.cs.princeton.edu
To reconstruct a path, follow parent pointers backward from the target vertex to the starting vertex, then reverse the order. For example, if parent[D] = B and parent[B] = A, the discovered path from A to D is A → B → D. Use a separate marker to indicate that the starting vertex has no parent.
However, interpreting “shortest” too broadly leads to errors. BFS guarantees the minimum number of edges only when all edges can be treated as having the same cost. If roads have different travel times or flights have different fares, a path using two edges may be cheaper or faster than one using a single edge. In that case, standard BFS is not a shortest-path algorithm by cost. Depending on the properties of the weights, consider dedicated weighted methods such as Dijkstra's algorithm or the Bellman-Ford algorithm. algs4.cs.princeton.edu
Therefore, BFS is a good fit for problems such as “How many degrees of connection separate two friends?” or “How many moves are needed to reach a point in a grid when moving one cell up, down, left, or right counts as one move?” In contrast, if the goal is the least time or lowest cost, first verify whether edge weights are truly equal.
Why Does DFS Go Deep Before Backtracking?
DFS stands for Depth-First Search. From the current vertex, it chooses one unvisited neighbor and continues moving until it has explored a branch as deeply as possible. When it reaches a dead end, it returns to the previous vertex and looks for another neighbor that has not yet been explored. This process of returning is also called backtracking. ocw.mit.edu
DFS is easy to implement with recursive calls. When entering a vertex, first mark it visited, then call the same traversal function for every unvisited neighbor of that vertex. When a recursive call ends, control naturally returns to the point that called it, expressing the flow of going deep and then backtracking.
Recursion is not the only option. DFS can also be implemented iteratively with an explicit stack. A stack is a LIFO (Last In, First Out) data structure, meaning that the last item added is the first item removed. By removing the most recently discovered vertex first, you can produce depth-first behavior. In a recursive implementation, the program's call stack performs this role implicitly. ocw.mit.edugh.cp-algorithms.com
Parent pointers created by DFS can also show one path from the starting vertex to a vertex. However, that path is not guaranteed to have the minimum number of edges. Because DFS follows its first chosen branch as deeply as possible, it may discover a shorter path in another branch only later. ocw.mit.edu
What Types of Structural Analysis Use DFS?
DFS shows its value when analyzing graph structure rather than simply checking reachability. Finding connected components is a representative example. In an undirected graph, running DFS once from any unvisited vertex finds all vertices connected to it as one group. Starting DFS again from a remaining unvisited vertex finds another group.
Cycle detection is another common application of DFS. A cycle is a structure in which following edges can bring you back to the starting point or to a vertex already on the current path. In a directed graph, you can detect a cycle by distinguishing whether you encounter a vertex that is already on the current recursive path. This is why you must distinguish between a vertex that has merely been visited once and one that is currently on the traversal path.
Topological sorting arranges directed dependencies, such as prerequisite relationships between tasks, into an order. It is possible only in a directed acyclic graph, or DAG. A DAG is a directed graph with no cycle that returns to its starting point by following edge directions. If a cycle exists, a contradiction arises—for example, B must finish before A and A must finish before B—so no linear ordering can satisfy all edges. A method that uses DFS finishing order is one foundation for topological sorting. algs4.cs.princeton.edu
Finding strongly connected components is also an important topic based on DFS. A strongly connected component is a set of vertices in a directed graph where any two vertices in the same group can reach each other. However, this problem is not solved with just one simple DFS; it requires an algorithmic construction that uses traversal order and edge directions. algs4.cs.princeton.edu
What Problems Occur Without Visited Markers?
In a general graph, a visited array or set is not optional; it is essential for termination and correctness. For example, if A and B are connected, you can go from A to B and then back from B to A. Without checking visited status, DFS can recursively alternate between A and B forever, and BFS can place the same vertex into the queue multiple times. ocw.mit.edu
The term visited can be divided slightly differently depending on the implementation. In BFS, a vertex is usually marked as “discovered” the moment it is added to the queue. In DFS, it is common to mark a vertex visited immediately when entering its function. More sophisticated directed-graph analysis may distinguish among an unvisited state, a state currently being explored, and a completed state.
The principle of visiting each vertex only once is directly tied to traversal efficiency. If you do not expand vertices that have already been processed, then with adjacency lists you inspect each vertex and edge only a limited number of times. Also, if you assign a parent pointer only when a vertex is first discovered, it is clear which path first discovered that vertex.
To traverse an entire graph, you need an outer loop. Examine every vertex in turn, and whenever you find one that has not yet been visited, start a new BFS or DFS from it. In an undirected graph, this produces a traversal by connected component. In a directed graph, it successively processes ranges reachable in the chosen edge directions. ocw.mit.edu
Why Does Time Complexity Depend on Graph Representation?
The time complexity of BFS and DFS is often given as . This is the standard analysis when using adjacency lists. An adjacency list stores the list of directly connected neighbors for each vertex. With visited markers, each vertex is processed once, and edges are checked while scanning neighbor lists, so the total work is proportional to the number of vertices plus the number of edges. ocw.mit.edu
Additional space is usually . This includes the visited array, parent array, and BFS queue or DFS stack. For recursive DFS, the call stack required by recursion depth is also included in the additional space. It is useful to distinguish between the space used to store the graph itself and the extra space used by the traversal algorithm. ocw.mit.edu
An adjacency matrix stores the existence of an edge for each pair of vertices in a table. To find a vertex's neighbors, you may need to inspect every possible vertex. Therefore, BFS or DFS using an adjacency matrix can typically take time. For sparse graphs with few edges, adjacency lists are particularly efficient because they scan only actually connected neighbors. ocw.mit.edu
| Representation | How neighbors are checked | Typical traversal time |
|---|---|---|
| Adjacency list | Iterate over the list of actually connected neighbors | |
| Adjacency matrix | Check connections to every possible vertex |
Complexity notation describes how resource use tends to grow as input size increases. Actual runtime is also affected by vertex identifiers, the adjacency-list implementation, memory layout, and the size of the portion reachable from the traversal's starting point. Still, when choosing an algorithm, it is sensible to first check whether the graph is sparse and how it is represented.
Is the Actual BFS or DFS Visitation Order Fixed?
No. BFS follows the principle of processing closer levels first, and DFS follows the principle of exploring the current branch deeply, but which vertex is visited first within the same level or which branch is explored first among several neighbors depends on the storage order of adjacent vertices. gh.cp-algorithms.comgh.cp-algorithms.com
For example, if A's neighbor list is ordered B, C, BFS generally discovers B first. If the list is changed to C, B, C may be discovered first. This difference can have a larger effect in DFS. If the first chosen neighbor changes, the deeply explored branch itself changes, along with the traversal tree and DFS paths created through parent pointers.
This fact matters when evaluating an algorithm's result. If a problem requires “the lexicographically first visitation order,” you must sort adjacency lists or specify a priority rule. In contrast, if you only need reachability, the number of connected components, or minimum-edge distances, the detailed order within the same level or depth may not be central to the result.
In particular, when implementing DFS iteratively with a stack, the order in which neighbors are pushed can be the reverse of the order in which they are actually removed. If you want the same visitation order as a recursive implementation using a given adjacency-list order, you need to intentionally adjust the direction in which neighbors are pushed onto the stack. This is not a different definition of DFS; it is an implementation difference caused by LIFO behavior.
What Are Common Misconceptions and Mistakes?
First is the misconception that BFS solves every kind of shortest-path problem. As discussed earlier, BFS guarantees the minimum number of edges in an unweighted graph. If weights differ, one move does not necessarily have the same value as another, so the problem model itself changes. algs4.cs.princeton.edualgs4.cs.princeton.edu
Second is the assumption that DFS always uses less memory than BFS. Including visited arrays and traversal state, both algorithms can generally use additional space. The maximum size of the queue or stack can differ for particular graph shapes and implementations, but asymptotic complexity alone does not establish an unconditional advantage for either one. ocw.mit.edu
Third is the belief that recursive DFS is safe for every input. In a graph with a very long depth, recursion depth also becomes large. You should account for the call stack limit of the language and execution environment; in such cases, an iterative implementation with an explicit stack can be more practical. It is also important to understand that the recursive call stack is part of DFS's additional space. ocw.mit.edu
Fourth is treating a directed graph as though it were undirected. The existence of an edge from A to B does not mean you can travel from B to A. When storing input in adjacency lists, an undirected graph usually adds an edge to both vertices' lists, while a directed graph adds it only to the source vertex's list. This difference changes the meaning of reachability, connectivity, and cycles. ocw.mit.edu
Fifth is mistaking a traversal result for a unique correct path. When several paths have the same minimum number of edges, BFS records one of them through parent pointers. DFS can also produce different paths depending on neighbor order. If the path itself needs a priority, sorting rules or additional conditions must be specified in the problem.
What Criteria Should You Use When Choosing for a Problem?
It is best to first put the goal into words. If the question only asks, “Can it be reached from the starting point?”, both BFS and DFS are possible, and you can choose based on the implementation environment and the analysis needed afterward. If you need the minimum number of edges, such as “How many identical moves are needed to arrive?”, BFS is the natural choice. If you need to follow a path deeply while analyzing structure, or if the point at which you return matters, DFS is likely appropriate.
Next, check what the edges mean. Determine whether every move has the same cost or whether weights such as time, distance, or cost are involved. If weights exist, do not directly apply BFS's shortest-path property. Also check in advance whether the graph is directed, whether cycles are possible, and whether you need to examine the entire graph. ocw.mit.edualgs4.cs.princeton.edu
The selection criteria can be summarized as follows.
| Situation or question | Method to consider first | Conditions to note |
|---|---|---|
| Minimum number of moves, level-by-level expansion | BFS | Edge costs must be equal |
| Simple reachability | BFS or DFS | Explores only the part reachable from the starting point |
| Finding connected components as groups | DFS or BFS | Repeat traversal for each unvisited vertex |
| Analyzing cycles, topological order, or strongly connected structure | DFS-based methods | Topological sorting is possible only in a DAG |
| Shortest paths with differing times or costs | Another weighted shortest-path method | Standard BFS guarantees do not apply |
Finally, consider input size and representation. For a sparse graph, adjacency lists and the standard analysis for BFS and DFS are a good fit. In environments where recursion depth may be a problem, consider iterative DFS. If visitation order affects grading or business rules, adjacency-list ordering is also part of the design.
Conclusion: Traversal Goals and Conditions Matter More Than Names
BFS and DFS are different strategies for thoroughly traversing a graph. BFS uses a queue to expand from nearby vertices and has the strength of providing minimum-edge paths in unweighted graphs. DFS uses recursion or a stack to explore one branch deeply and backtrack, forming the basis for many methods that work with graph structure, including connected components, cycles, and topological sorting in DAGs. ocw.mit.edualgs4.cs.princeton.edu
Both require visited markers and generally have the same asymptotic time complexity when using adjacency lists. Therefore, the key to choosing between them is not a single label such as speed, but what defines a shortest path, whether edges are weighted, how direction and cycles should be interpreted, and whether the whole graph must be processed. Distinguishing these conditions first lets you use BFS and DFS for the right purpose.