Поиск самой длинной петли в графе

Как говорили учителя в школе — а теперь для самых умных задача со звездочкой. «Longest cycle in a graph» отмечена как сложная задача на leetcode. Давайте разберем как её решить.

Дан массив, который описывает ориентированный граф. В каждой ячейке массива содержится номер ячейки, которая должна следовать за данной, согласно графу. Если ячейка содержит -1, то тут путь в графе прерывается.

Граф может содержать петли, т.е. зацикленные сегменты. И наша задача найти длину самой длинной петли, если они есть.

Пример графа с петлей:

Ячейка под номером ноль ссылается на саму себя, так у нас получается петля с длиной пути равной единице.

А в следующем графе нет петель:

Все пути заканчиваются элементом, ссылающимся на индекс -1.

Алгоритм

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

Я привел этот вариант для того, чтобы показать те места, которые требуют оптимизации или иного подхода.

Проблемы подхода:

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

Во-вторых, если текущий путь собирать в отдельный массив, а потом проверять, не содержится ли очередной узел в текущем пути, то только эти расчёты сделают наши вычислительные затраты >= N^2. Что для графа с числом узлов порядка 10^5 будет уже не приемлемым.

Решение

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

Представим, что мы выбрали произвольный узел графа и начали двигаться вдоль пути этого графа. Двигаясь, мы помечаем пройденные узлы уникальным номером пути (pathID). У нас возможны следующие ситуации:

  • очередной узел еще не был посещен, тогда мы помечаем его pathID;
  • очередной узел был уже посещен, но он принадлежит другому пути, значит мы нашли вход в уже пройденный участок графа, который мы рассмотрели ранее;
  • очередной узел был уже посещен, при этом отмечен тем же pathID, которым мы маркируем узлы текущего пути. Это значит, что мы движемся в петле. Но нам не известна длина петли. Потребуется пройти вдоль текущего пути еще раз, чтобы узнать длину петли.

В целом, это рабочий алгоритм, но при разборе кода я обращу внимание на еще один нюанс.

Вариант реализации на typescript:

Надеюсь, вы уловили в чем заключается нюанс продолжения перебора узлов, когда мы отталкиваемся от последнего из обработанных.

Написать комментарий

Мало букафф? Читайте есчо !

Задача - число островов

Март 25, 2023 г.

Разбираю задачу #200 с литкода, число островов (number of islands). Задан двумерный массив, в котором участки суши помечены как "1", а участки воды - как "0". Требуется подсчитать число получившихся островов. При этом считается, что участки суши образуют ...

Читать

TS: функция преобразования к каноническому пути

Март 15, 2023 г.

Увидел эту задачу на leetcode - https://leetcode.com/problems/simplify-path/, где не так часто встречаются задачи близкие к практиктическому программированию. Ранее уже приводил решение подобной задачи для PHP. Здесь порешаем её уже на TS. Задача ...

Читать

 

Комментарии к «Поиск самой длинной петли в графе»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: