Difference Between BFS and DFS: A Comprehensive Guide

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.

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.

Difference Between BFS and DFS

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.