Join Our 4-Week Free Gen AI Course with select Programs.

Request a callback

or Chat with us on

# Difference Between BFS and DFS: A Comprehensive Guide

Internship Assurance
DevOps & Cloud Engineering

Breadth-First Search (BFS) and Depth-First Search (DFS) are fundamental algorithms used in computer science for graph traversal. They help in exploring the nodes and edges of a graph, making them essential for various applications like pathfinding, network analysis, and game development.

In this guide, we will explain what BFS and DFS are, highlight the key differences between them, and discuss their uses and advantages. By the end, you will have a clear understanding of these algorithms and know when to use each one.

## What is BFS?

Breadth-first search (BFS) is a graph traversal algorithm that starts from a given node and explores all its neighbouring nodes at the present depth before moving on to nodes at the next depth level. It uses a queue to keep track of nodes to be explored next and ensures that nodes are visited in the order of their distance from the start node.

### Step-by-Step Algorithm

1. Initialize Data Structures:

• Create a queue and enqueue the starting node.
• Mark the starting node as visited.

2. While Queue is Not Empty:

• Dequeue a node from the queue.
• Process the dequeued node (e.g., print it or record it).
• For each unvisited neighbour of the dequeued node:
• Mark the neighbour as visited.
• Enqueue the neighbour.

### BFS Code

Java

import java.util.*;

public class BFS {

// Function to perform BFS traversal from a given start node

public static void bfs(int start, List<List<Integer>> adjList) {

boolean[] visited = new boolean[adjList.size()]; // Array to keep track of visited nodes

Queue<Integer> queue = new LinkedList<>(); // Queue for BFS

// Initialize by marking the start node as visited and enqueue it

visited[start] = true;

queue.add(start);

while (!queue.isEmpty()) {

int node = queue.poll(); // Dequeue a node

System.out.print(node + ” “); // Process the node (e.g., print it)

// Explore all unvisited neighbours of the dequeued node

for (int neighbor : adjList.get(node)) {

if (!visited[neighbor]) {

visited[neighbor] = true; // Mark the neighbor as visited

queue.add(neighbor); // Enqueue the neighbor

}

}

}

}

public static void main(String[] args) {

List<List<Integer>> adjList = Arrays.asList(

Arrays.asList(1, 2), // Node 0

Arrays.asList(0, 3, 4), // Node 1

Arrays.asList(0, 4), // Node 2

Arrays.asList(1, 4, 5), // Node 3

Arrays.asList(1, 2, 3), // Node 4

Arrays.asList(3) // Node 5

);

System.out.println(“BFS starting from node 0:”);

bfs(0, adjList);

}

}

Output:

BFS starting from node 0:

0 1 2 3 4 5

C++

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

// Function to perform BFS traversal from a given start node

void bfs(int start, const vector<vector<int>>& adjList) {

vector<bool> visited(adjList.size(), false); // Vector to keep track of visited nodes

queue<int> q; // Queue for BFS

// Initialize by marking the start node as visited and enqueue it

visited[start] = true;

q.push(start);

while (!q.empty()) {

int node = q.front(); // Dequeue a node

q.pop();

cout << node << ” “; // Process the node (e.g., print it)

// Explore all unvisited neighbors of the dequeued node

for (int neighbor : adjList[node]) {

if (!visited[neighbor]) {

visited[neighbor] = true; // Mark the neighbor as visited

q.push(neighbor); // Enqueue the neighbor

}

}

}

}

int main() {

vector<vector<int>> adjList = {

{1, 2}, // Node 0

{0, 3, 4}, // Node 1

{0, 4}, // Node 2

{1, 4, 5}, // Node 3

{1, 2, 3}, // Node 4

{3} // Node 5

};

cout << “BFS starting from node 0:n”;

bfs(0, adjList);

return 0;

}

Python

from collections import deque

def bfs(start, adj_list):

visited = [False] * len(adj_list) # List to keep track of visited nodes

queue = deque([start]) # Queue for BFS, initialized with the start node

visited[start] = True # Mark the start node as visited

while queue:

node = queue.popleft() # Dequeue a node

print(node, end=’ ‘) # Process the node (e.g., print it)

# Explore all unvisited neighbours of the dequeued node

for neighbor in adj_list[node]:

if not visited[neighbor]:

visited[neighbor] = True # Mark the neighbor as visited

queue.append(neighbor) # Enqueue the neighbor

adj_list = [

[1, 2], # Node 0

[0, 3, 4], # Node 1

[0, 4], # Node 2

[1, 4, 5], # Node 3

[1, 2, 3], # Node 4

[3] # Node 5

]

print(“BFS starting from node 0:”)

bfs(0, adj_list)

JavaScript

function bfs(start, adjList) {

const visited = new Array(adjList.length).fill(false); // Array to keep track of visited nodes

const queue = [start]; // Queue for BFS, initialized with the start node

visited[start] = true; // Mark the start node as visited

while (queue.length > 0) {

const node = queue.shift(); // Dequeue a node

console.log(node); // Process the node (e.g., print it)

// Explore all unvisited neighbors of the dequeued node

for (const neighbor of adjList[node]) {

if (!visited[neighbor]) {

visited[neighbor] = true; // Mark the neighbor as visited

queue.push(neighbor); // Enqueue the neighbor

}

}

}

}

const adjList = [

[1, 2], // Node 0

[0, 3, 4], // Node 1

[0, 4], // Node 2

[1, 4, 5], // Node 3

[1, 2, 3], // Node 4

[3] // Node 5

];

console.log(“BFS starting from node 0:”);

bfs(0, adjList);

### Complexity Analysis

• Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. Each node is enqueued and dequeued exactly once, and each edge is explored once.
• Space Complexity: O(V), where V is the number of vertices. This space is used for the visited array and the queue.

Also read: What is data structure

## What is DFS?

Depth-First Search (DFS) is another fundamental graph traversal algorithm. Unlike BFS, which explores nodes level by level, DFS dives deep into the graph, following one branch as far as possible before backtracking. This approach is useful for scenarios like pathfinding in mazes, topological sorting, and cycle detection in graphs.

### Step-by-Step Algorithm

1. Initialize Data Structures:
• Use a stack to manage the traversal.
• Mark the starting node as visited and push it onto the stack.
1. While Stack is Not Empty:
• Pop a node from the stack.
• Process the popped node (e.g., print it or record it).
• For each unvisited neighbour of the popped node:
• Mark the neighbour as visited.
• Push the neighbour onto the stack.

### DFS Code

Java

import java.util.*;

public class DFS {

// Function to perform DFS traversal from a given start node

public static void dfs(int start, List<List<Integer>> adjList) {

boolean[] visited = new boolean[adjList.size()]; // Array to keep track of visited nodes

Stack<Integer> stack = new Stack<>(); // Stack for DFS

// Initialize by marking the start node as visited and pushing it onto the stack

visited[start] = true;

stack.push(start);

while (!stack.isEmpty()) {

int node = stack.pop(); // Pop a node from the stack

System.out.print(node + ” “); // Process the node (e.g., print it)

// Explore all unvisited neighbors of the popped node

for (int neighbor : adjList.get(node)) {

if (!visited[neighbor]) {

visited[neighbor] = true; // Mark the neighbor as visited

stack.push(neighbor); // Push the neighbor onto the stack

}

}

}

}

public static void main(String[] args) {

List<List<Integer>> adjList = Arrays.asList(

Arrays.asList(1, 2), // Node 0

Arrays.asList(0, 3, 4), // Node 1

Arrays.asList(0, 4), // Node 2

Arrays.asList(1, 4, 5), // Node 3

Arrays.asList(1, 2, 3), // Node 4

Arrays.asList(3) // Node 5

);

System.out.println(“DFS starting from node 0:”);

dfs(0, adjList);

}

}

Output:

DFS starting from node 0:

0 2 4 3 5 1

C++

#include <iostream>

#include <vector>

#include <stack>

using namespace std;

// Function to perform DFS traversal from a given start node

void dfs(int start, const vector<vector<int>>& adjList) {

vector<bool> visited(adjList.size(), false); // Vector to keep track of visited nodes

stack<int> s; // Stack for DFS

// Initialize by marking the start node as visited and pushing it onto the stack

visited[start] = true;

s.push(start);

while (!s.empty()) {

int node = s.top(); // Pop a node from the stack

s.pop();

cout << node << ” “; // Process the node (e.g., print it)

// Explore all unvisited neighbors of the popped node

for (int neighbor : adjList[node]) {

if (!visited[neighbor]) {

visited[neighbor] = true; // Mark the neighbor as visited

s.push(neighbor); // Push the neighbor onto the stack

}

}

}

}

int main() {

vector<vector<int>> adjList = {

{1, 2}, // Node 0

{0, 3, 4}, // Node 1

{0, 4}, // Node 2

{1, 4, 5}, // Node 3

{1, 2, 3}, // Node 4

{3} // Node 5

};

cout << “DFS starting from node 0:n”;

dfs(0, adjList);

return 0;

}

Python

def dfs(start, adj_list):

visited = [False] * len(adj_list) # List to keep track of visited nodes

stack = [start] # Stack for DFS, initialized with the start node

visited[start] = True # Mark the start node as visited

while stack:

node = stack.pop() # Pop a node from the stack

print(node, end=’ ‘) # Process the node (e.g., print it)

# Explore all unvisited neighbors of the popped node

for neighbor in adj_list[node]:

if not visited[neighbor]:

visited[neighbor] = True # Mark the neighbor as visited

stack.append(neighbor) # Push the neighbor onto the stack

adj_list = [

[1, 2], # Node 0

[0, 3, 4], # Node 1

[0, 4], # Node 2

[1, 4, 5], # Node 3

[1, 2, 3], # Node 4

[3] # Node 5

]

print(“DFS starting from node 0:”)

dfs(0, adj_list)

JavaScript

function dfs(start, adjList) {

const visited = new Array(adjList.length).fill(false); // Array to keep track of visited nodes

const stack = [start]; // Stack for DFS, initialized with the start node

visited[start] = true; // Mark the start node as visited

while (stack.length > 0) {

const node = stack.pop(); // Pop a node from the stack

console.log(node); // Process the node (e.g., print it)

// Explore all unvisited neighbors of the popped node

for (const neighbor of adjList[node]) {

if (!visited[neighbor]) {

visited[neighbor] = true; // Mark the neighbor as visited

stack.push(neighbor); // Push the neighbour onto the stack

}

}

}

}

const adjList = [

[1, 2], // Node 0

[0, 3, 4], // Node 1

[0, 4], // Node 2

[1, 4, 5], // Node 3

[1, 2, 3], // Node 4

[3] // Node 5

];

console.log(“DFS starting from node 0:”);

dfs(0, adjList);

### Complexity Analysis

• Time Complexity: O(V + E), where V is the number of vertices (nodes), and E is the number of edges. Each node is pushed and popped from the stack exactly once, and each edge is explored once.
• Space Complexity: O(V), where V is the number of vertices. This space is used for the visited array and the stack.
Internship Assurance
DevOps & Cloud Engineering

## Difference Between BFS and DFS

 Criteria BFS (Breadth-First Search) DFS (Depth-First Search) Order of Traversal Level by level Depth first, then backtracking Data Structure Used Queue Stack Memory Usage Generally higher due to storing all nodes at the current level Generally lower as it uses recursion or stack to store nodes Optimal for Finding Shortest path in unweighted graphs Paths in problems involving game theory, puzzles, etc. Completeness Complete, will find a solution if one exists Not guaranteed to find the shortest path if one exists Space Complexity O(V) where V is the number of vertices O(V) where V is the number of vertices Time Complexity O(V + E) where V is vertices and E is edges O(V + E) where V is vertices and E is edges Backtracking Does not involve backtracking Involves backtracking Applications Finding the shortest path, level-order traversal, and more Topological sorting, solving puzzles, and more Performance on Dense Graphs It can be slower due to high memory usage More efficient due to lower memory usage

## Conclusion

In conclusion, BFS and DFS are essential algorithms for graph traversal, each with its strengths and ideal use cases. BFS is optimal for finding the shortest path in unweighted graphs, while DFS is suited for problems requiring deep exploration, such as puzzles and topological sorting. Understanding these differences will help you choose the right algorithm for your specific needs, ensuring efficient and effective problem-solving in various applications.

FAQs
BFS explores nodes level by level using a queue, while DFS dives deep into each branch using a stack.
Use BFS when you need to find the shortest path in an unweighted graph or explore nodes closest to the start node first.
DFS is ideal for problems requiring deep exploration, such as puzzles, pathfinding in mazes, and topological sorting.
Both BFS and DFS have a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.
BFS is complete and will find a solution if one exists. DFS does not guarantee the shortest path and might not find a solution in some cases if there are cycles.

Book a free counselling session

Get a personalized career roadmap

Get tailored program recommendations

Explore industry trends and job opportunities

Programs tailored for your success

Popular

Data Science

Technology

Finance

Management

Future Tech

Upskill with expert articles
View all
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.

## Professional Diploma in UX Design

Blogs
Reviews
Events
In the News
About Us
Contact us
Learning Hub
Privacy policy and Terms of use

© 2024 Hero Vired. All rights reserved