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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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