Графы — одна из базовых структур данных в IT. Они используются в навигаторах, соцсетях, рекомендательных системах, поиске маршрутов, компиляторах и сетевой инфраструктуре.
Что такое граф
Граф состоит из:
- вершин — объекты
- рёбер — связи между ними
Примеры:
- пользователи и дружба в соцсети
- города и дороги
- веб-страницы и ссылки
- сервисы и зависимости в микросервисной архитектуре
Как представляют граф в памяти
• Матрица смежности
Таблица N x N, где 1 означает наличие ребра между вершинами, 0 — отсутствие.
Подходит для плотных графов, но требует много памяти: O(V²).
• Список смежности
Для каждой вершины хранится список соседей.
Это самый популярный вариант на практике: память O(V + E), удобно обходить соседей.
Обход графа: зачем нужен
Обход позволяет:
- находить путь между вершинами
- искать компоненты связности
- определять циклы
- строить порядок обработки зависимостей
- решать задачи маршрутизации и анализа сетей
BFS — обход в ширину 🌐
BFS проходит граф “по слоям”: сначала все ближайшие вершины, потом следующий уровень.
Обычно используется очередь.
Когда полезен:
- поиск кратчайшего пути в невзвешенном графе
- поиск ближайшего объекта
- анализ уровней удалённости
- обход сетей и деревьев
Сложность:
- O(V + E) — по времени
- O(V) — по памяти
Главное преимущество BFS: он находит кратчайший путь по числу рёбер в невзвешенном графе.
DFS — обход в глубину 🕳️
DFS идёт как можно глубже по одной ветке, а затем возвращается назад.
Обычно реализуется через:
- рекурсию
- стек
Когда полезен:
- поиск компонент связности
- проверка на циклы
- топологическая сортировка
- задачи backtracking
- анализ структуры графа
Сложность:
- O(V + E) — по времени
- O(V) — по памяти
BFS или DFS: что выбрать? 🤔
- Нужен кратчайший путь в невзвешенном графе — BFS
- Нужно исследовать структуру, проверить циклы или пройти все ветки — DFS
- Нужен послойный обход — BFS
- Нужен компактный и часто более простой код — DFS
Где это встречается в реальной разработке 💻
- маршруты в картах
- граф зависимостей пакетов
- crawling сайтов
- рекомендации “друзья друзей”
- CI/CD и порядок сборки модулей
- анализ сетевой топологии
Понимание графов, BFS и DFS — это база для алгоритмов, системного дизайна и собеседований. Без них сложно уверенно двигаться в backend, data engineering, DevOps и computer science.
📌 Сохраните пост, если хотите быстро освежить тему перед собеседованием или разбором алгоритмов.
И загляните в подборку каналов про IT — там много полезного по алгоритмам, разработке и карьере 🚀