Graph traversal algorithms are essential in many domains of computer science, ranging from network routing to game development. Among the most fundamental graph traversal techniques, Depth First Search (DFS) and Breadth First Search (BFS) stand out as the most commonly used algorithms. Understanding the differences between Depth First Search vs Breadth First Search can significantly enhance problem-solving strategies. In this article, we will dive into the key differences between Depth First Search vs Breadth First Search, compare their functionalities, and provide multiple problem-solving examples with Java solutions.
Table of Contents
What is Depth First Search?
Definition:
Depth First Search is a traversal algorithm that explores as deeply as possible along each branch before backtracking. It dives deeper into the graph before moving to the next unvisited node, essentially exploring nodes in a depth-first manner. The algorithm uses a stack (either explicitly or via recursion) to keep track of the nodes to be visited.
How DFS Works:
- Start at a given node (or the root node if it’s a tree).
- Visit the node and explore all its unvisited neighbors recursively or iteratively.
- Once you reach a node with no unvisited neighbors, backtrack to the last node with unvisited neighbors, repeating the process until all nodes are visited.
DFS can be implemented either iteratively with an explicit stack or recursively.
Example of Depth First Search:
Consider a graph represented as follows:
A / \ B C | | D E
The DFS traversal starting from A will follow the path: A → B → D → C → E.
DFS Algorithm in Java (Iterative Version):
import java.util.*;
public class DFSAlgo {
// DFSAlgo using Stack
public static void dfsUsingStack(Map<String, List<String>> graph, String start) {
Set<String> visited = new HashSet<>();
Stack<String> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
String node = stack.pop();
if (!visited.contains(node)) {
System.out.print(node + " ");
visited.add(node);
}
for (String neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D"));
graph.put("C", Arrays.asList("A", "E"));
graph.put("D", Arrays.asList("B"));
graph.put("E", Arrays.asList("C"));
System.out.println("DFS Traversal:");
dfsUsingStack(graph, "A");
}
}
Output:
DFS Traversal: A B D C E
Key Notes:
- Depth First Search is implemented using recursion or using an explicit stack.
- It explores the graph in a depth-first manner, diving as deep as possible into one branch before backtracking.
Also check: Recursive Algorithm/ Recursion Algorithm Explained with Examples
What is Breadth First Search?
Definition:
Breadth First Search explores the graph level by level. It starts at the root node and explores all its immediate neighbors before moving to the next level of nodes. It uses a queue to keep track of the nodes that need to be explored.
How BFS Works:
- Start at the root node.
- Explore all the neighbors at the current level.
- Move to the next level, visiting all the neighbors at that depth, and continue until all nodes are visited.
BFS is ideal for scenarios where you need to explore all possible nodes at the current level before diving deeper, which makes it especially useful for finding the shortest path in an unweighted graph.
Example of Breadth First Search:
Consider the following graph:
A / \ B C | | D E
The BFS traversal starting from node A will follow this path: A → B → C → D → E.
BFS Algorithm in Java:
import java.util.*;
public class BFSAlgo {
// BFSAlgo using Queue
public static void bfsUsingQueue(Map<String, List<String>> graph, String start) {
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
visited.add(start);
queue.add(start);
while (!queue.isEmpty()) {
String node = queue.poll();
System.out.print(node + " ");
for (String neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D"));
graph.put("C", Arrays.asList("A", "E"));
graph.put("D", Arrays.asList("B"));
graph.put("E", Arrays.asList("C"));
System.out.println("BFS Traversal:");
bfsUsingQueue(graph, "A");
}
}
Output:
BFS Traversal: A B C D E
Key Notes:
- Breadth First Search is implemented using a queue to manage nodes as they are explored.
- It processes nodes level by level, making it ideal for finding the shortest path in an unweighted graph.
Depth First Search vs Breadth First Search: Key Differences
Both Depth First Search and Breadth First Search are used for graph traversal, but they differ in their approach, memory usage, and applications. Here’s a more detailed comparison:
1. Traversal Strategy:
- Depth First Search: Explores as deeply as possible into one branch before backtracking.
- Breadth First Search: Explores all nodes at the current level before moving to the next level.
2. Data Structure Used:
- Depth First Search: Uses a stack (either explicitly or implicitly via recursion).
- Breadth First Search: Uses a queue.
3. Memory Complexity:
- Depth First Search: The memory usage is usually smaller because it only needs to store the nodes in the current path being explored.
- Breadth First Search: Generally consumes more memory because it stores all the nodes at a particular depth level in the queue.
4. Completeness:
- Depth First Search: It may not always find the shortest path, especially in unweighted graphs.
- Breadth First Search: Always finds the shortest path in unweighted graphs because it processes nodes level by level.
5. Time Complexity:
- Both Depth First Search and Breadth First Search have a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph. The constant factors may differ depending on the implementation and graph structure.
6. Applications:
- Depth First Search:
- Cycle detection in directed graphs.
- Topological sorting (especially in directed acyclic graphs).
- Solving puzzles and games (like mazes).
- Pathfinding in certain cases where you need to explore deep before backtracking.
- Breadth First Search:
- Shortest path finding in unweighted graphs.
- Level-order traversal in trees.
- Finding connected components in undirected graphs.
- Web crawlers and social network analysis.
Also check: Master Binary Search Recursive & Binary Search Iterative – 5 Leetcode Java Solutions
Example Problems and Solutions
Problem 1: Finding the Shortest Path in an Unweighted Graph
Given an unweighted graph, find the shortest path from a start node to an end node using Breadth First Search.
Solution:
Breadth First Search is the ideal algorithm for this problem because it guarantees the shortest path in an unweighted graph.
import java.util.*;
public class ShortestPathBFS {
public static int bfsShortestPath(Map<String, List<String>> graph, String start, String end) {
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
Map<String, Integer> distance = new HashMap<>();
visited.add(start);
queue.add(start);
distance.put(start, 0);
while (!queue.isEmpty()) {
String node = queue.poll();
if (node.equals(end)) {
return distance.get(node);
}
for (String neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
distance.put(neighbor, distance.get(node) + 1);
}
}
}
return -1; // No path found
}
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D"));
graph.put("C", Arrays.asList("A", "E"));
graph.put("D", Arrays.asList("B"));
graph.put("E", Arrays.asList("C"));
System.out.println("Shortest Path from A to D: " + bfsShortestPath(graph, "A", "D"));
}
}
Output:
Shortest Path from A to D: 2
Explanation:
- BFS explores nodes level by level, ensuring the shortest path is found between A and D in 2 steps.
Problem 2: Cycle Detection in a Directed Graph
Detect whether a cycle exists in a directed graph using Depth First Search.
Solution:
DFS can be used to detect cycles by tracking the nodes currently being explored (recursion stack). If a node is encountered that is already in the recursion stack, a cycle is detected.
import java.util.*;
public class CycleDetectionDFS {
public static boolean dfsCycleDetection(Map<String, List<String>> graph, String node, Set<String> visited, Set<String> recStack) {
if (recStack.contains(node)) return true;
if (visited.contains(node)) return false;
visited.add(node);
recStack.add(node);
for (String neighbor : graph.get(node)) {
if (dfsCycleDetection(graph, neighbor, visited, recStack)) {
return true;
}
}
recStack.remove(node);
return false;
}
public static boolean hasCycle(Map<String, List<String>> graph) {
Set<String> visited = new HashSet<>();
Set<String> recStack = new HashSet<>();
for (String node : graph.keySet()) {
if (!visited.contains(node)) {
if (dfsCycleDetection(graph, node, visited, recStack)) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B"));
graph.put("B", Arrays.asList("C"));
graph.put("C", Arrays.asList("A")); // This creates a cycle
System.out.println("Graph contains cycle: " + hasCycle(graph));
}
}
Output:
Graph contains cycle: true
Explanation:
- The Depth First Search algorithm checks for back edges using the recursion stack to detect cycles. A cycle is found because node A is revisited via node C.
Problem 3: Level-Order Traversal in a Binary Tree
Given a binary tree, perform a level-order traversal using Breadth First Search and return the nodes at each level.
Solution:
In Breadth First Search, each level is processed by exploring all nodes at that level before moving to the next level.
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class TreeLevelOrder {
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
result.add(level);
}
return result;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
List<List<Integer>> result = levelOrder(root);
System.out.println("Level Order Traversal:");
for (List<Integer> level : result) {
System.out.println(level);
}
}
}
Output:
Level Order Traversal: [1] [2, 3] [4, 5]
Explanation:
- BFS processes nodes level by level, ensuring that nodes on each level are explored before moving deeper into the tree.
Conclusion: DFS vs BFS
The choice between DFS vs BFS depends on the specific requirements of the problem you are solving. Here’s a quick recap:
- Depth First Search is ideal for exploring deep structures, backtracking problems, and tasks like cycle detection or topological sorting.
- Breadth First Search is optimal for problems where you need the shortest path in an unweighted graph or to explore a tree level by level.
By understanding the differences between these two traversal algorithms and knowing when to apply them, you can make your code more efficient and your problem-solving approach more effective. Whether you’re solving graph problems, tree traversal tasks, or pathfinding, knowing the strengths of DFS and BFS will help you optimize your solution.
To keep yourself up to date with our latest content, please subscribe to our newsletter by dropping your email address here: Signup for Our Newsletter.
Please follow us on Medium.
Further Reading
- How to crack technical interview – Google, Amazon & more
- How to Prepare for and Crack the Coding Interview
- Machine Coding Round – What is it & how to crack it
- Digital Wallet Design – Machine Coding Round Solution
- Best Coding Platform To Become A Coding Expert
- The ultimate guide to interview preparation