Purfe

Learn, create and have fun with Python

# 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 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) - 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) 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``````