Поиск пути по графу

Поиск пути по графу

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

Что такое путь

Путь в графе — это последовательность вершин, в которой каждые соседние соединены ребром. Путь начинается в одной вершине и заканчивается в другой. Между двумя вершинами может быть несколько разных путей, а может не быть ни одного, если они не связаны.

Запись связей таблицей

Связи графа удобно записать таблицей: на пересечении строки и столбца ставят знак, если между вершинами есть ребро.

Из / в	А	Б	В	Г
А	—	есть	есть	нет
Б	есть	—	нет	есть
В	есть	нет	—	есть
Г	нет	есть	есть	—

Разбор примера

Найдём все пути из вершины А в вершину Г по таблице выше. Будем двигаться по рёбрам, не возвращаясь в уже пройденные вершины:

А -> Б -> Г А -> В -> Г А -> Б -> ... (других нет) Итого: 2 пути

Получилось два разных пути: через Б и через В. Чтобы ничего не пропустить, перебор ведут по порядку, на каждом шаге выписывая все вершины, куда можно перейти.

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

Длина пути и кратчайший маршрут

Длиной пути называют число рёбер в нём. В примере оба пути из А в Г имеют длину 2, то есть состоят из двух переходов. Если бы рёбрам приписали расстояния, можно было бы искать кратчайший путь — тот, у которого сумма расстояний наименьшая. Именно такую задачу решает навигатор, выбирая самую короткую или быструю дорогу из множества возможных.

Путь	Через какие вершины	Длина
Первый	А, Б, Г	2
Второй	А, В, Г	2

Связные и несвязные графы

Граф называют связным, если между любыми двумя его вершинами есть путь. Если же какие-то вершины нельзя соединить ни одним путём, граф несвязный — он распадается на отдельные части. Понять, связен ли граф, важно: например, если карта дорог несвязна, до некоторых городов вообще не доехать.

Где применяется

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

Сколько путей: складываем ответы у вершин

Если в ориентированном графе нет циклов, количество путей можно найти без выписывания каждого маршрута. Обрабатывайте вершины в таком порядке, чтобы все предшественники очередной вершины уже были посчитаны. Такой порядок называют топологическим. Расположение точки левее на рисунке само по себе не гарантирует правильного порядка — смотрите на стрелки.

У начальной вершины запишите 1: это один пустой маршрут до начала движения. У недостижимых вершин — 0. У каждой следующей вершины сложите числа у всех вершин, откуда в неё непосредственно входят стрелки. Последний переход различает эти группы путей, поэтому повторного учёта нет. Рассматриваем граф без параллельных рёбер.

Редакционный граф

Зададим все стрелки списком: А→Б, А→В, Б→Г, В→Г, В→Д, Г→Д, Г→Е, Д→Е. Других связей нет.

Вершина	Расчёт	Путей от А
А	Начало	1
Б	От А	1
В	От А	1
Г	Б + В	2
Д	В + Г	3
Е	Г + Д	5

Обязательная и запрещённая вершины

Через Г проходят 2 пути до Г и 2 продолжения от Г до Е: напрямую и через Д. Итого 2 · 2 = 4. Без Г остаётся один: А→В→Д→Е. Проверка: 4 + 1 = 5.

Чтобы исключить вершину, уберите её и все связанные с ней стрелки, затем пересчитайте. Чтобы пройти через две заданные вершины, учитывайте допустимый порядок посещения. Условие «через одну из двух, но не через обе» требует исключить совместное посещение, а не просто сложить два ответа с пересечением.

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

Справочные материалы: Поиск пути по графу — исходная тема; Поиск пути по графу — исходная тема; Поиск пути по графу — исходная тема. Связанные уроки: Дерево вариантов и перебор, Циклы с известным числом повторений.

Кратко о главном

• Граф состоит из вершин и соединяющих их рёбер.
• Путь — это цепочка вершин, где соседние соединены ребром.
• Связи графа удобно записывать таблицей.
• При переборе путей помечают пройденные вершины, чтобы не зациклиться.