🎨 Floodfill = BFS на графе

🎨 Floodfill = BFS на графе

Помните заливку в Paint? Это не просто "красивая фишка" — это обход графа в действии.

Сетка пикселей — это граф:

- Каждый пиксель = вершина (node)

- Соседи пикселя = рёбра (edges)

- Стены = вершины, которых нет

Floodfill — это BFS (поиск в ширину) на этом графе.

Алгоритм:

neighbour_offsets = [(+1, 0), (0, +1), (-1, 0), (0, -1)]

tracked = set((x, y)) # Посещённые вершины

to_paint = [(x, y)] # Очередь BFS

while to_paint:

vertex = to_paint.pop(0) # Берём из начала очереди

process(vertex)

for dx, dy in neighbour_offsets:

nx, ny = vertex[0] + dx, vertex[1] + dy

if (nx, ny) not in tracked and is_valid(nx, ny):

tracked.add((nx, ny)) # Отмечаем как посещённую

to_paint.append((nx, ny)) # Добавляем в очередь

set используется для отслеживания уже добавленных пикселей. Без этого на больших сетках один пиксель обработается дважды и алгоритм станет медленным.

Где это используется:

✓ Графические редакторы (заливка, волшебная палочка)

✓ Поиск в графах (BFS/DFS-вариант)

✓ Волнообразное распространение

✓ Анализ связных компонентов в сетках

В прикрепленной статье автор показывает интерактивную демонстрацию — видишь в реальном времени, как цвет распространяется.

Идеально для подготовки к собеседованиям и понимания алгоритмов на графах. 🎯

📖 Полная статья