В этом уроке ты
- Узнаешь, что такое граф и как его можно представить.
- Поймешь, зачем учить графы: где они пригодятся на собеседованиях и в работе.
- Подготовишься к изучению ключевых алгоритмов обхода графов: DFS и BFS.
Раскраска по номерам
Представь, что у тебя есть раскраска, где каждый элемент — это небольшая клетка определённого цвета. У тебя есть инструмент «заливка», который работает так:
- Закрашиваются все соседние клетки (сверху, снизу, слева и справа), которые имеют такой же цвет, как и клетка, на которую ты нажал.
- При этом клетки по диагонали не считаются соседними.
Нужно посчитать, сколько всего «заливок» (нажатий на кнопку) нужно, чтобы раскрасить все клетки в нужные цвета.
Подсчёт заливок
На картинке выше понадобилось 4 заливки. Это значит, что в данной «раскраске» есть 4 отдельные области одинакового цвета, на которые заливка может распространиться за один раз.
Это легко!
Когда картинка маленькая, такое количество легко посчитать вручную. Но если картинка очень большая, скажем, 10 000 × 10 000 клеток, то вручную это уже практически нереально.
Зато можно написать программу, которая всё посчитает.
Интересный факт: задача про «раскраску по номерам» — это реальный пример задачи с собеседований в крупных IT-компаниях (BigTech).
Графы
Граф — это способ описать набор объектов (вершин) и связи между ними (рёбра).
Представь вершины как «города» в стране, а рёбра — как «дороги», соединяющие эти города. Если между двумя «городами» есть дорога, значит в графе между соответствующими вершинами существует ребро (изображение 1).
Как связаны графы с задачей про заливку
В задаче с заливкой каждая клетка — это вершина графа, а ребро возникает между двумя вершинами, если соответствующие клетки соприкасаются (слева, справа, сверху или снизу) и имеют одинаковый цвет.
Зачем нужны графы
Если ты хочешь успешно проходить алгоритмические собеседования, без графов не обойтись. На такие темы чаще дают задания опытным разработчикам, но порой они встречаются и у Junior, поэтому лучше готовиться заранее.
Графы важны и для тех, кто планирует работать в крупных IT-компаниях (BigTech). Они встречаются не только во время собеседований, но и в реальных проектах: от систем рекомендаций в социальных сетях до поиска оптимальных маршрутов.
Понимание графовых алгоритмов поможет выделиться на собеседовании и повысить твою ценность как специалиста.
Что нужно знать для собеседования
Первым делом нужно освоить два ключевых алгоритма:
- Обход в глубину (DFS)
- Обход в ширину (BFS)
С их помощью ты научишься:
- Находить все вершины (клетки), которые образуют одну область.
- Считать количество таких областей (как в задаче про раскраску).
- Искать пути и связи между вершинами.
Дальше, больше!
Скорее переходи к следующему уроку, чтобы научиться писать обходы графов и решить свою первую задачу с собеседования.