Everything You Need to Know About BFS and DFS algorithms

BFS and DFS are two fundamental graph traversal algorithms that have many practical applications in computer science. In this article, we’ll explore the key differences between these two algorithms and their advantages and disadvantages.

Applications of BFS and DFS

DFS and BFS algorithms are commonly used to solve a wide range of problems, particularly those that involve searching or exploring through a graph or a tree-like structure. Here are some examples of problems that can be solved using DFS and BFS:

DFS:

• Finding a path from a starting node to a goal node in a graph
• Detecting cycles in a graph
• Generating all possible permutations or combinations of a set of elements
• Topological sorting of a directed acyclic graph
• Finding all connected components in a graph
• Traversing a tree to search for a particular node or pattern

BFS:

• Finding the shortest path between two nodes in an unweighted graph
• Generating/solving mazes
• Finding the minimum number of moves required to solve a puzzle (sliding tile puzzles
• Searching for a node at a fixed distance from the starting node
• Crawling the web (web scraping)
• Exploring all nodes at a particular distance from a starting node

Note that both BFS and DFS can be used to solve a given problem, and sometimes they can be used interchangeably. The choice of algorithm depends on the specific problem requirements and constraints. In general, BFS is better for finding the shortest path in an unweighted graph or finding connected components. While DFS is better suited for finding solutions that require exploring deeper into the graph or tree, such as finding a path between two nodes or traversing a tree. DFS is also commonly used for the topological sorting of directed acyclic graphs (DAGs).

Advantages and disadvantages

Both BFS and DFS have their own advantages and disadvantages:

BFS and DFS Implementation

To provide an illustration of BFS and DFS implementation, let’s take the FloodFill problem on LeetCode as an example.

BFS

Time complexity: O(n + e), where n is the number of nodes and e is the number of edges.
Space complexity: O(n) where n is the number of nodes in a graph

def floodFill(image, sr, sc, newColor):
    # Get the original color of the starting pixel
    originalColor = image[sr][sc]

    # If the new color is the same as the original color, no need to do anything
    if originalColor == newColor:
        return image
Time complexity: O(n + e), where n is the number of <strong>n</strong>odes and e is the number of <strong>e</strong>dges.
Space complexity: O(n) where n is the number of <strong>n</strong>odes in a graph
    # Set up a queue to store pixels that need to be processed
    queue = [(sr, sc)]

    # Loop until all pixels in the queue have been processed
    while queue:
        # Get the coordinates of the next pixel to process
        row, col = queue.pop(0)

        # If the pixel is already the new color, skip it
        if image[row][col] == newColor:
            continue

        # If the pixel is the original color, change it to the new color
        if image[row][col] == originalColor:
            image[row][col] = newColor

            # Add neighboring pixels to the queue if thTime complexity: O(n + e), where n is the number of <strong>n</strong>odes and e is the number of <strong>e</strong>dges.
Space complexity: O(n) where n is the number of <strong>n</strong>odes in a graphey are the original color
            if row > 0:
                queue.append((row - 1, col))
            if row < len(image) - 1:
                queue.append((row + 1, col))
            if col > 0:
                queue.append((row, col - 1))
            if col < len(image[0]) - 1:
                queue.append((row, col + 1))

    # Return the modified image
    return image

DFS

Time complexity: O(n + e), where n is the number of nodes and e is the number of edges.
Space complexity: O(n) where n is the number of nodes in a graph

class Solution(object):
    def floodFill(self, image, sr, sc, color):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type color: int
        :rtype: List[List[int]]
        """
        # Define a DFS function for traversing the image
        def dfs(image, row, col, originalColor, color):
            # Check if the current pixel is out of bounds or if its color is not the original color
            if row < 0 or row >= len(image) or col < 0 or col >= len(image[0]) or image[row][col] != originalColor:
                return
            # Change the color of the current pixel to the new color
            image[row][col] = color
            # Recursively call the DFS function on the four neighboring pixels
            dfs(image, row - 1, col, originalColor, color) # Up
            dfs(image, row + 1, col, originalColor, color) # Down
            dfs(image, row, col - 1, originalColor, color) # Left
            dfs(image, row, col + 1, originalColor, color) # Right

        # Store the original color of the starting pixel
        originalColor = image[sr][sc]
        # If the original color is already the new color, return the image as is
        if originalColor == color:
            return image
        # Call the DFS function on the starting pixel
        dfs(image, sr, sc, originalColor, color)
        # Return the modified image
        return image