BFS/DFS: Breadth First Search & Depth First Search Tutorial

Avatar

By squashlabs, Last Updated: August 27, 2023

BFS/DFS: Breadth First Search & Depth First Search Tutorial

Introduction to BFS and DFS

Breadth First Search (BFS) and Depth First Search (DFS) are two fundamental graph traversal algorithms used in programming. These algorithms help to explore and search through the nodes or vertices of a graph in a systematic manner.

BFS is a graph traversal algorithm that starts at a given node and explores all its neighbors at the current depth level before moving on to the next depth level. It uses a queue data structure to keep track of the nodes to be visited.

DFS, on the other hand, explores as far as possible along each branch before backtracking. It uses a stack data structure to keep track of the nodes to be visited.

Let’s take a closer look at the definitions and basic concepts of BFS and DFS.

Related Article: How to Implement HTML Select Multiple As a Dropdown

Definitions and Basic Concepts

In BFS, the graph is traversed level by level. Starting from a given source node, BFS explores all the neighbors at the current level before moving on to the next level. This ensures that all nodes at a particular level are visited before moving deeper into the graph.

Here’s an example of BFS traversal on an undirected graph:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)
            visited.add(node)
            queue.extend(graph[node] - visited)

In DFS, the graph is traversed deeply into each branch before backtracking. Starting from a given source node, DFS explores as far as possible along each branch before backtracking to explore other branches.

Here’s an example of DFS traversal on a directed graph:

import java.util.Stack;

public class DFS {
    public void dfs(Graph graph, int start) {
        boolean[] visited = new boolean[graph.getNumVertices()];
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited[node]) {
                System.out.println(node);
                visited[node] = true;
                for (int neighbor : graph.getNeighbors(node)) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

Now that we have a basic understanding of BFS and DFS, let’s explore their implementations in algorithms.

Implementation of BFS in Algorithms

BFS is commonly used in various algorithms, such as finding the shortest path in an unweighted graph. One example is finding the shortest path between two nodes in a social network.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<int> shortestPath(const vector<vector<int>>& graph, int start, int end) {
    vector<int> path;
    vector<bool> visited(graph.size(), false);
    vector<int> prev(graph.size(), -1);
    queue<int> q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        if (current == end) {
            // Reconstruct the path
            int node = end;
            while (node != -1) {
                path.push_back(node);
                node = prev[node];
            }
            reverse(path.begin(), path.end());
            break;
        }

        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
                prev[neighbor] = current;
            }
        }
    }

    return path;
}

In this example, we use a queue to implement BFS and find the shortest path between the start and end nodes in an unweighted graph. The algorithm keeps track of visited nodes and the previous node in the shortest path.

Implementation of DFS in Algorithms

DFS is widely used in algorithms that require exploring all possible paths or detecting cycles in a graph. One example is detecting cycles in a directed graph.

function hasCycle(graph) {
    const visited = new Set();
    const stack = new Set();

    function dfs(node) {
        visited.add(node);
        stack.add(node);

        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                if (dfs(neighbor)) {
                    return true;
                }
            } else if (stack.has(neighbor)) {
                return true;
            }
        }

        stack.delete(node);
        return false;
    }

    for (const node of graph.keys()) {
        if (!visited.has(node)) {
            if (dfs(node)) {
                return true;
            }
        }
    }

    return false;
}

In this example, we use a recursive approach to implement DFS and detect cycles in a directed graph. The algorithm keeps track of visited nodes and nodes in the current recursion stack.

Now that we have explored the implementations of BFS and DFS, let’s move on to their specific use cases.

Related Article: How to Use If-Else Statements in Shell Scripts

BFS Use Case: Shortest Path in Unweighted Graph

BFS is particularly useful in finding the shortest path in an unweighted graph. One common use case is finding the shortest path between two nodes in a social network.

import java.util.*;

public class ShortestPath {
    public List<Integer> findShortestPath(Graph graph, int start, int end) {
        List<Integer> path = new ArrayList<>();
        boolean[] visited = new boolean[graph.getNumVertices()];
        int[] prev = new int[graph.getNumVertices()];
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int current = queue.poll();

            if (current == end) {
                // Reconstruct the path
                int node = end;
                while (node != -1) {
                    path.add(node);
                    node = prev[node];
                }
                Collections.reverse(path);
                break;
            }

            for (int neighbor : graph.getNeighbors(current)) {
                if (!visited[neighbor]) {
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                    prev[neighbor] = current;
                }
            }
        }

        return path;
    }
}

In this example, we use BFS to find the shortest path between the start and end nodes in an unweighted graph. The algorithm keeps track of visited nodes and the previous node in the shortest path.

DFS Use Case: Detecting Cycles in a Graph

DFS is often used to detect cycles in a graph. One example is detecting cycles in a directed graph.

def has_cycle(graph):
    visited = set()
    stack = set()

    def dfs(node):
        visited.add(node)
        stack.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in stack:
                return True

        stack.remove(node)
        return False

    for node in graph.keys():
        if node not in visited:
            if dfs(node):
                return True

    return False

In this example, we use a recursive approach to implement DFS and detect cycles in a directed graph. The algorithm keeps track of visited nodes and nodes in the current recursion stack.

BFS Best Practice: Choosing the Right Data Structures

To optimize BFS, it is important to choose the right data structures. In particular, using a queue and a set can enhance the performance of BFS.

Here’s an example of BFS implementation with optimized data structures:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)
            visited.add(node)
            queue.extend(graph[node] - visited)

In this example, we use a deque as a queue and a set as a visited set. The deque provides efficient pop and append operations, while the set ensures that each node is visited only once.

Related Article: The issue with Monorepos

DFS Best Practice: Recursive vs Non-Recursive Approaches

DFS can be implemented using both recursive and non-recursive approaches. The choice depends on the specific requirements of the problem and the characteristics of the graph.

Here’s an example of a non-recursive implementation of DFS using a stack:

import java.util.Stack;

public class DFS {
    public void dfs(Graph graph, int start) {
        boolean[] visited = new boolean[graph.getNumVertices()];
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited[node]) {
                System.out.println(node);
                visited[node] = true;
                for (int neighbor : graph.getNeighbors(node)) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

In this example, we use a stack to implement a non-recursive DFS traversal. The stack keeps track of the nodes to be visited, and the visited array ensures that each node is visited only once.

Real World Application of BFS: Web Crawling

BFS is widely used in web crawling, which involves systematically navigating through web pages to collect data or index them for search engines.

Here’s an example of BFS-based web crawling:

import requests
from collections import deque
from bs4 import BeautifulSoup

def web_crawl(start_url, target_word):
    visited = set()
    queue = deque([start_url])

    while queue:
        url = queue.popleft()
        if url not in visited:
            visited.add(url)
            response = requests.get(url)
            if target_word in response.text:
                print(f"Found target word '{target_word}' at URL: {url}")
            soup = BeautifulSoup(response.text, "html.parser")
            for link in soup.find_all("a"):
                queue.append(link.get("href"))

In this example, we use BFS to crawl web pages starting from a given URL. The algorithm checks for a target word in each visited page and collects all the links to further explore.

Real World Application of DFS: Topological Sorting

DFS is commonly used in topological sorting, which is the process of arranging the nodes of a directed graph in a linear order that respects the partial order of dependencies between the nodes.

Here’s an example of DFS-based topological sorting:

import java.util.*;

public class TopologicalSort {
    public List<Integer> topologicalSort(Graph graph) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();

        for (int node : graph.getNodes()) {
            if (!visited.contains(node)) {
                dfs(node, graph, visited, result);
            }
        }

        Collections.reverse(result);
        return result;
    }

    private void dfs(int node, Graph graph, Set<Integer> visited, List<Integer> result) {
        visited.add(node);

        for (int neighbor : graph.getNeighbors(node)) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, graph, visited, result);
            }
        }

        result.add(node);
    }
}

In this example, we use a recursive DFS approach to perform topological sorting on a directed graph. The algorithm keeps track of visited nodes and adds them to the result list in reverse order.

Related Article: 16 Amazing Python Libraries You Can Use Now

BFS Performance Consideration: Time and Space Complexity

Understanding the time and space complexity of BFS is crucial for evaluating its performance and scalability.

The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because BFS visits each vertex and each edge exactly once.

The space complexity of BFS is O(V), where V is the number of vertices in the graph. This is because BFS uses a queue to store the nodes to be visited, and the maximum number of nodes in the queue at any given time is the number of vertices.

DFS Performance Consideration: Stack Size Limitation

One important consideration when using DFS is the limitation on the maximum stack size. Recursive DFS implementations are prone to stack overflow errors if the graph is too large or has deep recursion levels.

To overcome this limitation, an iterative approach or an alternative data structure such as an explicit stack can be used in place of the function call stack.

For example, here’s an iterative DFS implementation using an explicit stack in Python:

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node)
            visited.add(node)
            stack.extend(neighbor for neighbor in graph[node] if neighbor not in visited)

In this example, we use an explicit stack to implement an iterative DFS traversal. The stack keeps track of the nodes to be visited, and the visited set ensures that each node is visited only once.

Advanced Technique: Iterative Deepening DFS

Iterative Deepening DFS (IDDFS) is an advanced technique that combines the advantages of both BFS and DFS. It gradually increases the maximum depth of DFS until the goal is found.

Here’s an example of IDDFS implementation in Python:

def iddfs(graph, start, goal, max_depth):
    for depth in range(max_depth + 1):
        visited = set()
        stack = [(start, 0)]

        while stack:
            node, current_depth = stack.pop()
            if node == goal:
                return True
            if current_depth < depth:
                visited.add(node)
                stack.extend((neighbor, current_depth + 1) for neighbor in graph[node] if neighbor not in visited)

    return False

In this example, IDDFS is implemented using a stack and a depth limit. The algorithm gradually increases the depth of DFS until either the goal is found or the maximum depth is reached.

Related Article: How to Use Generics in Go

Advanced Technique: Bidirectional BFS

Bidirectional BFS is an advanced technique that improves the efficiency of BFS by simultaneously searching from both the start and end nodes. It reduces the search space and can significantly speed up the search process, especially in large graphs.

Here’s an example of bidirectional BFS implementation in Java:

import java.util.*;

public class BidirectionalBFS {
    public boolean bidirectionalBfs(Graph graph, int start, int end) {
        Set<Integer> visitedStart = new HashSet<>();
        Set<Integer> visitedEnd = new HashSet<>();
        Queue<Integer> queueStart = new LinkedList<>();
        Queue<Integer> queueEnd = new LinkedList<>();

        visitedStart.add(start);
        visitedEnd.add(end);
        queueStart.offer(start);
        queueEnd.offer(end);

        while (!queueStart.isEmpty() && !queueEnd.isEmpty()) {
            if (queueStart.size() <= queueEnd.size()) {
                if (bfsStep(graph, visitedStart, queueStart, visitedEnd)) {
                    return true;
                }
            } else {
                if (bfsStep(graph, visitedEnd, queueEnd, visitedStart)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean bfsStep(Graph graph, Set<Integer> visited, Queue<Integer> queue, Set<Integer> target) {
        int current = queue.poll();

        for (int neighbor : graph.getNeighbors(current)) {
            if (visited.add(neighbor)) {
                queue.offer(neighbor);
                if (target.contains(neighbor)) {
                    return true;
                }
            }
        }

        return false;
    }
}

In this example, bidirectional BFS is implemented using two sets and two queues. The algorithm simultaneously performs BFS from both the start and end nodes, terminating when a common node is found or both queues become empty.

Code Snippet: BFS Implementation in Java

Here’s a code snippet showing the implementation of BFS in Java:

import java.util.*;

public class BFS {
    public void bfs(Graph graph, int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (!visited.contains(node)) {
                System.out.println(node);
                visited.add(node);
                for (int neighbor : graph.getNeighbors(node)) {
                    queue.offer(neighbor);
                }
            }
        }
    }
}

In this example, BFS is implemented using a queue and a visited set. The algorithm starts from a given start node and visits all the nodes in the graph, ensuring that each node is visited only once.

Code Snippet: DFS Implementation in Python

Here’s a code snippet showing the implementation of DFS in Python:

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node)
            visited.add(node)
            stack.extend(neighbor for neighbor in graph[node] if neighbor not in visited)

In this example, DFS is implemented using a stack and a visited set. The algorithm starts from a given start node and explores as far as possible along each branch before backtracking.

Related Article: Comparing GraphQL and Elasticsearch

Code Snippet: BFS in a Matrix Grid in C++

Here’s a code snippet showing the implementation of BFS in a matrix grid in C++:

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<pair<int, int>> directions{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void bfs(vector<vector<int>>& grid, int startRow, int startCol) {
    int numRows = grid.size();
    int numCols = grid[0].size();
    vector<vector<bool>> visited(numRows, vector<bool>(numCols, false));
    queue<pair<int, int>> q;

    q.push({startRow, startCol});
    visited[startRow][startCol] = true;

    while (!q.empty()) {
        auto [row, col] = q.front();
        q.pop();

        // Process the current cell
        cout << "Visiting cell (" << row << ", " << col << ")" << endl;

        // Explore the neighbors
        for (auto [dx, dy] : directions) {
            int newRow = row + dx;
            int newCol = col + dy;

            // Check if the neighbor is valid and not visited
            if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols && !visited[newRow][newCol]) {
                q.push({newRow, newCol});
                visited[newRow][newCol] = true;
            }
        }
    }
}

In this example, BFS is implemented to traverse a matrix grid. The algorithm starts from a given cell and explores its neighboring cells in a breadth-first manner, ensuring that each cell is visited only once.

Code Snippet: DFS with Backtracking in JavaScript

Here’s a code snippet showing the implementation of DFS with backtracking in JavaScript:

function dfs(board, row, col, word, index) {
    if (index >= word.length) {
        return true;
    }

    if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] !== word[index]) {
        return false;
    }

    const temp = board[row][col];
    board[row][col] = '#';

    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    for (const [dx, dy] of directions) {
        if (dfs(board, row + dx, col + dy, word, index + 1)) {
            board[row][col] = temp;
            return true;
        }
    }

    board[row][col] = temp;
    return false;
}

function exist(board, word) {
    const numRows = board.length;
    const numCols = board[0].length;

    for (let row = 0; row < numRows; row++) {
        for (let col = 0; col < numCols; col++) {
            if (dfs(board, row, col, word, 0)) {
                return true;
            }
        }
    }

    return false;
}

In this example, DFS with backtracking is implemented to solve the word search problem on a 2D board. The algorithm explores all possible paths in the board to find a given word, backtracking when a path leads to a dead end.

Code Snippet: Using BFS to Solve a Puzzle in C#

Here’s a code snippet showing the usage of BFS to solve a puzzle in C#:

using System;
using System.Collections.Generic;

public class PuzzleSolver
{
    public bool SolvePuzzle(Puzzle puzzle)
    {
        HashSet<string> visited = new HashSet<string>();
        Queue<Puzzle> queue = new Queue<Puzzle>();

        queue.Enqueue(puzzle);

        while (queue.Count > 0)
        {
            Puzzle currentPuzzle = queue.Dequeue();

            if (currentPuzzle.IsSolved())
            {
                return true;
            }

            visited.Add(currentPuzzle.ToString());

            List<Puzzle> nextPuzzles = currentPuzzle.GetNextPuzzles();

            foreach (Puzzle nextPuzzle in nextPuzzles)
            {
                if (!visited.Contains(nextPuzzle.ToString()))
                {
                    queue.Enqueue(nextPuzzle);
                }
            }
        }

        return false;
    }
}

In this example, BFS is used to solve a puzzle by exploring all possible moves from the initial state until a solution is found. The algorithm keeps track of visited states to avoid revisiting them.

Related Article: Exploring Elasticsearch Query Response Mechanisms

Error Handling in BFS and DFS Implementations

When implementing BFS and DFS algorithms, it’s important to handle potential errors and edge cases to ensure the correctness and robustness of the code.

Some common error scenarios to consider include:
– Handling invalid inputs such as null or empty graph.
– Checking for cycles or infinite loops in the graph traversal.
– Handling unreachable nodes or disconnected components in the graph.
– Ensuring appropriate data structures are used to prevent stack overflow errors or excessive memory usage.

By handling these error scenarios, you can improve the reliability and stability of your BFS and DFS implementations.

You May Also Like

What is Test-Driven Development? (And How To Get It Right)

Test-Driven Development, or TDD, is a software development approach that focuses on writing tests before writing the actual code. By following a set of steps, developers... read more

Agile Shortfalls and What They Mean for Developers

What is the best software development methodology to use? This question is the topic of hot debate during the project implementation stage. However, what you choose... read more

24 influential books programmers should read

The fast-paced world of programming demands that people remain up-to-date. In fact, getting ahead of the curve makes a programmer stand out in his professional field.... read more

The most common wastes of software development (and how to reduce them)

Software development is a complex endeavor that requires much time to be spent by a highly-skilled, knowledgeable, and educated team of people. Often, there are time... read more

Intro to Security as Code

Organizations need to adapt their thinking to protect their assets and those of their clients. This article explores how organizations can change their approach to... read more

The Path to Speed: How to Release Software to Production All Day, Every Day (Intro)

To shorten the time between idea creation and the software release date, many companies are turning to continuous delivery using automation. This article explores the... read more