Popular

Data Science

Technology

Finance

Management

Future Tech

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.

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.

**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.

**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);

**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**

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.

- Initialize Data Structures:

- Use a stack to manage the traversal.
- Mark the starting node as visited and push it onto the stack.

- 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.

**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);

**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

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 |

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

What are the main differences between BFS and DFS?

BFS explores nodes level by level using a queue, while DFS dives deep into each branch using a stack.

When should I use BFS?

Use BFS when you need to find the shortest path in an unweighted graph or explore nodes closest to the start node first.

When is DFS more suitable?

DFS is ideal for problems requiring deep exploration, such as puzzles, pathfinding in mazes, and topological sorting.

What are the time complexities of BFS and DFS?

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.

Do BFS and DFS guarantee finding a solution?

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.

Privacy policy and Terms of use

© 2024 Hero Vired. All rights reserved