Graph traversal is a cornerstone of computer science, enabling the exploration of nodes and edges in graphs. Two fundamental traversal strategies are Breadth‑First Search (BFS) and Depth‑First Search (DFS). This tutorial walks you through their theory, implementations in multiple programming languages, complexity analysis, and practical tips for real‑world applications.
Breadth‑First Search (BFS) Overview
BFS explores a graph level by level, starting from a source vertex and visiting all its immediate neighbors before moving to the next depth level. It is particularly useful for finding the shortest path in unweighted graphs, checking bipartiteness, and performing level order traversal in trees.
BFS Algorithm Steps
- Enqueue the
sourcevertex and mark it as visited. - While the queue is not empty:
- Dequeue a vertex
u. - For each unvisited neighbor
vofu: - Mark
vas visited and enqueuev.
Iterative BFS Implementation – Python
from collections import deque
def bfs(graph, start):
visited = set()
order = []
q = deque([start])
visited.add(start)
while q:
vertex = q.popleft()
order.append(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
q.append(neighbor)
return order
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print(bfs(graph, 'A')) # Output: ['A', 'B', 'C', 'D', 'E', 'F']Iterative BFS Implementation – Java
import java.util.*;
public class BFS {
public static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
List<Integer> order = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
return order;
}
public static void main(String[] args) {
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 3));
graph.put(2, Arrays.asList(4, 5));
graph.put(3, Arrays.asList(6));
graph.put(4, Collections.emptyList());
graph.put(5, Arrays.asList(6));
graph.put(6, Collections.emptyList());
System.out.println(bfs(graph, 1)); // [1, 2, 3, 4, 5, 6]
}
}Iterative BFS Implementation – C++
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
vector<int> bfs(const vector<vector<int>>& adj, int start) {
unordered_set<int> visited;
vector<int> order;
queue<int> q;
q.push(start);
visited.insert(start);
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : adj[u]) {
if (visited.find(v) == visited.end()) {
visited.insert(v);
q.push(v);
}
}
}
return order;
}
int main() {
vector<vector<int>> graph = {
{}, // 0 (unused)
{2,3}, // 1
{4,5}, // 2
{6}, // 3
{}, // 4
{6}, // 5
{} // 6
};
vector<int> result = bfs(graph, 1);
for (int v : result) cout << v << " "; // 1 2 3 4 5 6
return 0;
}BFS Time & Space Complexity
- Time Complexity: O(V + E) – each vertex and edge is processed once.
- Space Complexity: O(V) for the visited set and the queue.
Depth‑First Search (DFS) Overview
DFS dives as deep as possible along each branch before backtracking. It can be implemented recursively or iteratively (using a stack). DFS is ideal for tasks such as topological sorting, detecting cycles, solving puzzles, and exploring connected components.
DFS Algorithm Steps (Recursive)
- Visit the current vertex
uand mark it as visited. - For each neighbor
vofu: - If
vis not visited, recursively perform DFS onv.
Recursive DFS Implementation – Python
def dfs(graph, start, visited=None, order=None):
if visited is None:
visited = set()
if order is None:
order = []
visited.add(start)
order.append(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited, order)
return order
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print(dfs(graph, 'A')) # Output: ['A', 'B', 'D', 'E', 'F', 'C']Iterative DFS Implementation – Java
import java.util.*;
public class DFS {
public static List<Integer> dfs(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
List<Integer> order = new ArrayList<>();
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited.contains(node)) {
visited.add(node);
order.add(node);
// push neighbors in reverse order for natural ordering
List<Integer> neighbors = graph.getOrDefault(node, Collections.emptyList());
for (int i = neighbors.size() - 1; i >= 0; i--) {
int neighbor = neighbors.get(i);
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
return order;
}
public static void main(String[] args) {
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 3));
graph.put(2, Arrays.asList(4, 5));
graph.put(3, Arrays.asList(6));
graph.put(4, Collections.emptyList());
graph.put(5, Arrays.asList(6));
graph.put(6, Collections.emptyList());
System.out.println(dfs(graph, 1)); // [1, 2, 4, 5, 6, 3]
}
}DFS Time & Space Complexity
- Time Complexity: O(V + E) – same as BFS because each vertex and edge is examined once.
- Space Complexity: O(V) for the visited set and recursion stack (or explicit stack).
BFS vs DFS – Quick Comparison
| Property | BFS | DFS |
|---|---|---|
| Exploration Order | Level by level (breadth) | Depth first (branch) |
| Typical Use‑Cases | Shortest path in unweighted graph, level order traversal | Topological sort, cycle detection, puzzle solving |
| Data Structure Used | Queue (FIFO) | Stack (LIFO) – recursive call stack or explicit stack |
| Memory Consumption | Higher for wide graphs | Higher for deep graphs (recursion depth) |
“Breadth‑first search is the most obvious method to find the shortest path in an unweighted graph.” – Robert Sedgewick
parent of each visited node during BFS to reconstruct the shortest path after the traversal finishes.Practical Example – Finding the Shortest Path with BFS
Below is a complete Python function that returns the shortest path between two vertices in an unweighted graph using BFS.
from collections import deque
def bfs_shortest_path(graph, start, goal):
visited = set([start])
parent = {start: None}
q = deque([start])
while q:
cur = q.popleft()
if cur == goal:
# reconstruct path
path = []
while cur is not None:
path.append(cur)
cur = parent[cur]
return path[::-1]
for nxt in graph[cur]:
if nxt not in visited:
visited.add(nxt)
parent[nxt] = cur
q.append(nxt)
return None # no path found
# Example graph
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print(bfs_shortest_path(graph, 'A', 'F')) # Output: ['A', 'C', 'F']Summary
Frequently Asked Questions
Q: Can BFS be used on weighted graphs?
A: BFS finds the shortest path only in unweighted or uniformly weighted graphs. For weighted graphs, algorithms like Dijkstra’s or Bellman‑Ford are appropriate.
Q: Is DFS guaranteed to visit all vertices in a disconnected graph?
A: No. A single DFS call explores only the component containing the start vertex. To visit every vertex, run DFS from each unvisited vertex (or use a loop that iterates over all vertices).
Q: What is the difference between tree DFS and graph DFS?
A: In a tree, there are no cycles, so a simple recursive DFS suffices. In a general graph you must maintain a visited set to avoid infinite loops caused by cycles.
Quick Quiz
Q. Which data structure does BFS primarily rely on?
- Stack
- Queue
- Priority Queue
- HashMap
Answer: Queue
BFS uses a FIFO queue to ensure vertices are processed in the order they are discovered, achieving level‑order exploration.
Q. What is the worst‑case space complexity of recursive DFS on a graph with V vertices?
- O(1)
- O(log V)
- O(V)
- O(E)
Answer: O(V)
The recursion stack can grow up to the depth of the graph, which in the worst case equals the number of vertices.