Algorithms
BFS & DFS (Intro)
Difficulty: Beginner
Swap a queue for a stack inside a graph traversal and you flip from breadth-first to depth-first behavior. The visited-vertex tracking is identical, the neighbor expansion is identical, and yet one explores level by level while the other...
BFS & DFS (Intro)
Swap a queue for a stack inside a graph traversal and you flip from breadth-first to depth-first behavior. The visited-vertex tracking is identical, the neighbor expansion is identical, and yet one explores level by level while the other dives down the longest path first. That single data-structure swap is the entire difference between the two most-used graph algorithms in the field.
BFS & DFS (Intro) walks through both. For BFS you will implement queue-based level-by-level exploration and use it to find shortest paths in unweighted graphs. For DFS you will see both the recursive form (which uses the call stack implicitly) and the iterative form with an explicit stack, and apply them to connectivity checks, path finding, and cycle detection. The lesson also covers the visited set that prevents infinite loops on cyclic graphs and contrasts graph traversal with tree traversal as a special case.
This lesson assumes you are comfortable with three structures from the data-structures track: Stack (LIFO) powers iterative DFS, Queue & Deque powers BFS, and Graphs: Representation Basics gives you the adjacency list or matrix that both algorithms read from.
Next, Hashing Techniques turns to a different building block, the hash map, which underpins many of the lookup-heavy patterns you will combine with traversal in later lessons.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain the difference between BFS (breadth-first) and DFS (depth-first) traversal strategies.
Implement BFS using a queue and a visited set to traverse a graph level by level.
Implement DFS using both recursion and an explicit stack.
Use a visited set to prevent infinite loops in graphs with cycles.
Analyze the time complexity O(V + E) and space complexity O(V) of both algorithms.
Determine when to use BFS vs DFS based on the problem requirements.
Why This Matters
01
BFS and DFS are the foundation of nearly all graph algorithms — from shortest paths to cycle detection to topological sorting.
02
BFS finds the shortest path in unweighted graphs, making it essential for problems like word ladder, maze solving, and network analysis.
03
DFS is the backbone of recursion-based graph problems: connected components, cycle detection, and backtracking on graphs.
04
Understanding when to use BFS vs DFS is a core interview skill that appears in 15-20% of coding interviews.
Key Terms
7 terms you'll encounter in this lesson
BFS (Breadth-First Search)
A graph traversal algorithm that explores all neighbors of the current node before moving to the next level. Uses a queue (FIFO) data structure.
DFS (Depth-First Search)
A graph traversal algorithm that explores as far as possible along each branch before backtracking. Uses a stack (LIFO) or recursion.
Visited set
A data structure (set or boolean array) that tracks which nodes have already been explored, preventing infinite loops in graphs with cycles.
Adjacency list
A graph representation where each node maps to a list of its neighbors. Commonly implemented as a dictionary/hash map.
Level-order traversal
Visiting all nodes at a given depth before moving to the next depth. BFS naturally produces a level-order traversal.
Connected component
A maximal group of nodes where every node can reach every other node. A graph can have multiple disconnected components.
Graph cycle
A path in a graph that starts and ends at the same node. Without a visited set, traversing a graph with cycles leads to infinite loops.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"BFS and DFS visit nodes in the same order"
BFS visits nodes level by level (closest neighbors first), while DFS goes deep along one path before exploring siblings. For the same graph, they produce very different visit orders.
"DFS always uses recursion"
DFS can be implemented iteratively using an explicit stack. The recursive version implicitly uses the call stack, but the iterative version gives you more control and avoids stack overflow for deep graphs.
"BFS always finds the shortest path"
BFS finds the shortest path only in unweighted graphs (or graphs where all edges have equal weight). For weighted graphs, you need Dijkstra's or Bellman-Ford algorithm.
"You don't need a visited set for trees"
Trees have no cycles, so technically you won't loop forever. But you still need to avoid revisiting the parent node. In practice, always use a visited set — it's cheap insurance and works for both trees and general graphs.