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

BFS (Breadth-first search)	DFS (Depth-first search)
Expands the shallowest unexplored node first.	Expands the deepest unexplored node first.
Uses a queue to keep track of nodes to explore.	Uses a stack (or recursion) to keep track of nodes to explore.
It guarantees to find the shortest path in an unweighted graph.	It may not guarantee to find the shortest path in an unweighted graph.
It can be used to find the connected components in an unweighted graph.	It can be used to solve problems such as finding strongly connected components in a directed graph.
Examples: finding the shortest path in a maze, finding the shortest path between two points on a map.	Examples: depth-first search is often used to traverse a tree, search for an element in a tree or graph, find a path between two nodes in a graph, etc.

Advantages and disadvantages

Both BFS and DFS have their own advantages and disadvantages:

Algorithm	Advantages	Disadvantages
BFS	– Guarantees the shortest path for unweighted graphs. – Finds the shallowest solution first. – Can be used to find all nodes at a certain depth level.	– Uses more memory than DFS – Slower than DFS for finding the first solution in large graphs. BFS requires keeping track of a queue, which can be slower than the recursion stack used by DFS. This is particularly true if the branching factor is high. – Requires a queue data structure, which can be slow and more complex to implement. BFS requires keeping track of a queue, which can be more complex to implement than the simple recursion used by DFS.
DFS	– Faster than BFS for finding the first solution in large graphs. DFS explores nodes in depth-first order, which can be faster than BFS if the target is relatively close to the starting point and there are few branching paths to explore. – Uses less memory because at a time it needs to store only a single path from the root to the leaf node. – Requires only a stack data structure, which is fast (but when implemented with recursion can be slow and less memory efficient)	– Does not guarantee the shortest path. DFS explores paths to the target in depth-first order, which may not be the shortest path. This can lead to suboptimal results if finding the shortest path is important. – Can get stuck in infinite loops in graphs with cycles – May overlook solutions that are deep in the graph – Can use a lot of memory. DFS explores paths to their fullest extent before backtracking, which can use a lot of memory if the branching factor is high.

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