Графы: пути между вершинами

Количество путей, кратчайший путь (BFS) и достижимые вершины ориентированного графа

Какой вопрос задаём графу

По одному на строку, «A B» — ребро из A в B

Откуда идём

Куда идём (для режимов путей и кратчайшего пути)

Нашли ошибку или хотите предложить улучшение?

Улучшить калькулятор «Графы: пути между вершинами»

Теория

Граф — это набор вершин и соединяющих их рёбер. Если у каждого ребра указано направление («A B» — ребро из A в B), граф называют ориентированным; если по ребру можно идти в обе стороны — неориентированным. Путь — это последовательность рёбер, по которой можно пройти из одной вершины в другую; для графа из задачи пути удобно записывать цепочкой вершин: \(A \to C \to D\).

Если разрешить проходить через одну и ту же вершину сколько угодно раз, в графе с циклом путей окажется бесконечно много: \(A \to B \to A \to B \to \ldots\) Поэтому в школьных задачах пути считают без повторного прохождения вершин — тогда число путей конечно и его можно честно перебрать. Кратчайший путь ищут обходом в ширину (BFS): алгоритм идёт «по слоям», сначала все вершины на расстоянии одного ребра, потом двух, и потому первым добирается до цели по самому короткому маршруту.

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

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

Пример с решением

  1. Условие. Граф с рёбрами A B, B C, A C, C D, B D (ориентированный). Сколько путей ведёт из A в D и каков кратчайший путь?
  2. Перебор. Выписываем все цепочки из A в D, в которых вершины не повторяются: \(A \to B \to C \to D\), \(A \to B \to D\), \(A \to C \to D\).
  3. Ответ по числу путей. Таких путей три.
  4. Кратчайший путь. Обход в ширину из A: на расстоянии 1 лежат B и C, на расстоянии 2 — D. Значит \(A \to B \to D\) (или \(A \to C \to D\)) — это 2 ребра.
  5. Достижимость. Из A достижимы все четыре вершины: A (0 рёбер), B и C (1 ребро), D (2 ребра).
  6. Проверка. Если рёбра считать двунаправленными, добавится ещё путь \(A \to C \to B \to D\), и ответ станет 4 — калькулятор в режиме «Рёбра в обе стороны» покажет именно это.

Главное

  • Путь без повторного прохождения вершин — конечный объект даже в графе с циклами.
  • Кратчайший путь по числу рёбер находит обход в ширину (BFS), его длина — \(d(A,B) = \min |P|\).
  • Достижимость — это множество всех вершин, до которых есть хотя бы один путь.
  • Рёбра и петли: дубли рёбер считаются один раз, петля «A A» пути не создаёт.