Теория графов: как навигатор находит путь, а соцсеть — друзей

Перекрёстки и дороги, люди и дружбы, страницы и ссылки — всё это математика видит одинаково: точки, соединённые линиями.

Граф — это не картинка, а способ мышления: сведи задачу к точкам и связям, и для неё уже придуман алгоритм.

Граф состоит из вершин (узлов) и рёбер (связей между ними). Перекрёстки — вершины, дороги — рёбра. Люди — вершины, дружба — рёбра. Эта простая абстракция оказалась настолько универсальной, что лежит в основе навигаторов, соцсетей, поисковиков и даже расписания авиарейсов.

Как навигатор прокладывает маршрут

Когда вы просите проложить путь от дома до работы, навигатор видит город как граф: тысячи перекрёстков-вершин и улиц-рёбер. У каждого ребра есть вес — например, время проезда с учётом пробок. Задача: найти путь с наименьшей суммой весов.

Классическое решение — алгоритм Дейкстры. Он работает как растекающаяся вода: от старта «волна» расходится во все стороны, всегда продолжая расти из ближайшей по времени точки. Когда волна достигает финиша, кратчайший путь найден.

Жадность, которая не подводит

Дейкстра на каждом шаге выбирает ещё не обработанную вершину с минимальным известным расстоянием — это жадный выбор. Удивительно, но для дорог с неотрицательными весами такая жадность гарантированно даёт оптимум. Если время проезда дано на 100 рёбрах, то и проверить нужно порядка этих рёбер, а не все маршруты подряд — иначе перебор занял бы вечность.

старт: расстояние 0
остальные: расстояние ∞
пока есть необработанные вершины:
    взять ближайшую необработанную (v)
    для каждого соседа u:
        если путь через v короче — обновить расстояние до u

Соцсеть как гигантский граф

В социальной сети вы — вершина, а каждая дружба — ребро. Подсказка «возможно, вы знакомы» рождается из простого наблюдения: если у вас и у незнакомца много общих друзей, вы, вероятно, тоже знакомы. Алгоритм считает общих соседей по графу и ранжирует кандидатов.

Отсюда же знаменитая теория шести рукопожатий: любые два человека на Земле связаны цепочкой в среднем из шести знакомств. На графе это означает, что его «диаметр» поразительно мал даже для миллиардов вершин.

Кратчайший путь по дружбам

А как соцсеть находит, что вы и знаменитость связаны через четырёх человек? Тем же поиском пути по графу — только здесь вес каждого ребра одинаков, поэтому работает более простой поиск в ширину: расходимся кольцами от вас, пока не наткнёмся на цель. Число колец и есть длина цепочки знакомств.

Почему пробки меняют маршрут

Граф города не статичен: веса рёбер живут своей жизнью. Утром улица свободна и её вес мал, в час пик она забита — и вес взлетает. Навигатор постоянно подкачивает свежие данные о скорости потока и пересчитывает кратчайший путь почти в реальном времени. Поэтому один и тот же отрезок дороги система может то предлагать, то обходить стороной: с точки зрения графа изменилась «длина» ребра, и прежний маршрут перестал быть выгодным. Та же гибкость позволяет учитывать перекрытия, аварии и платные участки — всё это просто меняет веса, а алгоритм остаётся прежним.

Одна идея — тысячи применений

Поисковик ранжирует страницы, считая, кто на кого ссылается. Авиакомпания ищет дешёвую стыковку. Логистика развозит посылки. Все эти задачи — про одни и те же точки и связи. Выучив однажды, как устроены графы, вы начинаете узнавать их повсюду: математика подарила нам универсальный язык для описания связанного мира.