Flood-fill algorithms are widely used in computer graphics, image processing, and game development to determine the area connected to a particular node in a multi-dimensional array. This article compares the performance of two popular flood-fill algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS), providing technical insights, examples, and a detailed comparison using markdown formatting.

Understanding Flood-Fill Algorithms

Flood-fill algorithms operate by filling a connected region in a multi-dimensional space. The most common applications are in paint bucket tools in image editing software and boundary filling in game terrain generation.

Depth-First Search (DFS)

DFS is a recursive algorithm that explores as far as possible along a single branch before backtracking. It is implemented using a stack data structure, either explicitly with a user-defined stack or implicitly through function calls.

Breadth-First Search (BFS)

BFS explores the neighbor nodes at the present depth before moving on to nodes at the next depth level. It uses a queue data structure, which stores nodes in a First-In-First-Out (FIFO) manner.

Algorithm Performance

Depth-First Search (DFS)

• Time Complexity: $O(n \times m)$, where $n$ is the number of rows and $m$ is the number of columns. This complexity arises because DFS potentially visits every cell in the 2D space.
• Space Complexity: $O(n \times m)$ in the worst case, due to the stack used to store the recursive call stack. This can be expensive in terms of memory usage.
• Strengths: Efficient in scenarios where the area to be filled is compact, with relatively few recursive calls made before hitting a boundary.
• Weaknesses: Susceptible to stack overflow if the fill area is large, due to the depth of recursion.

Breadth-First Search (BFS)

• Time Complexity: $O(n \times m)$, similar to DFS because each cell may need to be visited once to determine connectivity.
• Space Complexity: $O(n \times m)$ due to the need to store all nodes in the current layer for the next level of exploration.
• Strengths: Handles large contiguous regions effectively without the risk of a stack overflow since it maintains a queue to manage nodes.
• Weaknesses: May require significant memory overhead due to the storage of all neighbor nodes, leading to increased space complexity.

Example Comparisons

Consider the following pseudo-code implementations and performance analysis for both algorithms.

DFS Example