Graph Traversal BFS and DFS from Scratch (2026)
Graph traversal is the process of visiting every vertex and edge in a graph exactly once. Two fundamental algorithms for graph traversal are Breadth-First Search (BFS) and Depth-First Search (DFS). BFS explores the graph level by level, visiting all neighbors at the current depth before moving deeper. DFS explores as far as possible along each branch before backtracking. Understanding these algorithms is essential for solving a wide range of problems including shortest path, connectivity, cycle detection, and topological sorting.
In this tutorial, we will implement both BFS and DFS iteratively and recursively, analyze their time and space complexities, and explore their real-world applications. By the end, you will be able to choose the right traversal strategy for any graph problem.
Breadth-First Search (BFS)
BFS uses a queue data structure to explore all neighbors at the current depth before moving to the next level. Starting from a source vertex, we enqueue it, then repeatedly dequeue a vertex, mark it as visited, and enqueue all its unvisited neighbors. This guarantees that vertices are visited in order of their distance from the source, making BFS ideal for finding the shortest path in unweighted graphs.
BFS runs in O(V + E) time where V is the number of vertices and E is the number of edges. The space complexity is O(V) for the queue and visited set.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
result = []
while queue:
vertex = queue.popleft()
result.append(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
graph = {
0: [1, 2], 1: [0, 3, 4], 2: [0, 5],
3: [1], 4: [1, 5], 5: [2, 4]
}
print(bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]Depth-First Search (DFS) - Iterative
DFS uses a stack data structure (or recursion) to explore as deep as possible along each branch before backtracking. The iterative implementation uses an explicit stack, pushing the starting vertex, then repeatedly popping a vertex, marking it visited, and pushing all unvisited neighbors. This approach avoids the recursion depth limit and is more memory efficient for very deep graphs.
DFS is useful for detecting cycles, finding strongly connected components, solving puzzles, and topological sorting. The time complexity is O(V + E) and space complexity is O(V).
#include
#include
#include
#include
using namespace std;
vector dfsIterative(vector>& graph, int start) {
vector result;
unordered_set visited;
stack st;
st.push(start);
while (!st.empty()) {
int v = st.top(); st.pop();
if (visited.count(v)) continue;
visited.insert(v);
result.push_back(v);
for (int nb : graph[v])
if (!visited.count(nb)) st.push(nb);
}
return result;
} Depth-First Search (DFS) - Recursive
The recursive implementation of DFS is more elegant and closely mirrors the mathematical definition. We define a helper function that marks the current vertex as visited, adds it to the result, and recursively calls itself for each unvisited neighbor. The recursion naturally handles the backtracking when all neighbors have been visited.
Recursive DFS has the same time complexity O(V + E) but uses O(V) stack space due to the call stack. For very large graphs, the iterative version is preferred to avoid stack overflow.
class Graph {
private int V;
private List> adj;
Graph(int v) {
V = v;
adj = new ArrayList<>();
for (int i = 0; i < v; i++)
adj.add(new ArrayList<>());
}
void dfsUtil(int v, boolean[] visited, List result) {
visited[v] = true;
result.add(v);
for (int nb : adj.get(v))
if (!visited[nb]) dfsUtil(nb, visited, result);
}
} BFS vs DFS Comparison
BFS and DFS have different characteristics that make them suitable for different problems. BFS uses more memory but guarantees the shortest path in unweighted graphs. DFS uses less memory and is better for problems involving backtracking. BFS explores in layers while DFS explores as deep as possible before backtracking.
Choose BFS when you need shortest paths or level-order processing. Choose DFS when you need to explore all possibilities, detect cycles, or find connected components. Both have the same time complexity O(V + E) for adjacency list representation.
from collections import deque
def bfs_shortest_path(graph, start, end):
visited = {start}
queue = deque([(start, [start])])
while queue:
vertex, path = queue.popleft()
if vertex == end: return path
for nb in graph[vertex]:
if nb not in visited:
visited.add(nb)
queue.append((nb, path + [nb]))
return None
def bfs_levels(graph, start):
visited = {start}
queue = deque([start])
levels = []
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
v = queue.popleft()
current_level.append(v)
for nb in graph[v]:
if nb not in visited:
visited.add(nb)
queue.append(nb)
levels.append(current_level)
return levelsFrequently Asked Questions
When to use BFS vs DFS?
Use BFS for shortest path in unweighted graphs, level-order traversal, or when the target is close to the source. Use DFS for cycle detection, topological sorting, maze solving, or when memory is limited.
What is the time complexity of BFS and DFS?
Both BFS and DFS run in O(V + E) time where V is the number of vertices and E is the number of edges when using an adjacency list. With adjacency matrix, both take O(V^2).
Can BFS find the shortest path in weighted graphs?
No, BFS only works for unweighted graphs or graphs where all edges have equal weight. For weighted graphs, use Dijkstra's algorithm or Bellman-Ford algorithm.
How to detect a cycle using DFS?
During DFS, if you encounter a vertex that is currently being visited (in the recursion stack), you have found a back edge, indicating a cycle. Maintain three states: unvisited, visiting, visited.
Originally published on Ayodhyyya. Last updated June 1, 2026.