Как говорили учителя в школе — а теперь для самых умных задача со звездочкой. «Longest cycle in a graph» отмечена как сложная задача на leetcode. Давайте разберем как её решить.
Дан массив, который описывает ориентированный граф. В каждой ячейке массива содержится номер ячейки, которая должна следовать за данной, согласно графу. Если ячейка содержит -1, то тут путь в графе прерывается.
Граф может содержать петли, т.е. зацикленные сегменты. И наша задача найти длину самой длинной петли, если они есть.
Пример графа с петлей:
|
1 |
[0] |
Ячейка под номером ноль ссылается на саму себя, так у нас получается петля с длиной пути равной единице.
А в следующем графе нет петель:
|
1 |
[-1, 2, -1] |
Все пути заканчиваются элементом, ссылающимся на индекс -1.
Алгоритм
Самый брутфорсовый вариант можно представить как следующий: мы берем каждый узел и пытаемся проходить путь по графу, начиная с выбранного узла. Путь собираем в специальный массив, чтобы можно было проверить для очередного узла — нет ли петли. Если цепочка обрывается (мы находим -1), то берем следующий узел. Если же мы попадаем в петлю, то измеряем её длину. Максимальную длину сохраняем.
Я привел этот вариант для того, чтобы показать те места, которые требуют оптимизации или иного подхода.
Проблемы подхода:
Во-первых, мы будем обходить одни и те же узлы многократно. Т.е. нужно как то помечать уже пройденные узлы, чтобы в дальнейшем их не рассматривать.
Во-вторых, если текущий путь собирать в отдельный массив, а потом проверять, не содержится ли очередной узел в текущем пути, то только эти расчёты сделают наши вычислительные затраты >= N^2. Что для графа с числом узлов порядка 10^5 будет уже не приемлемым.
Решение
Т.к. мы решили как то помечать посещенные узлы, то для решения второй проблемы будем отмечать их уникальным номером текущего пути. Тогда обнаружив, что очередной узел пути принадлежит тому же самому пути, мы автоматически определим, что находимся в петле.
Представим, что мы выбрали произвольный узел графа и начали двигаться вдоль пути этого графа. Двигаясь, мы помечаем пройденные узлы уникальным номером пути (pathID). У нас возможны следующие ситуации:
- очередной узел еще не был посещен, тогда мы помечаем его pathID;
- очередной узел был уже посещен, но он принадлежит другому пути, значит мы нашли вход в уже пройденный участок графа, который мы рассмотрели ранее;
- очередной узел был уже посещен, при этом отмечен тем же pathID, которым мы маркируем узлы текущего пути. Это значит, что мы движемся в петле. Но нам не известна длина петли. Потребуется пройти вдоль текущего пути еще раз, чтобы узнать длину петли.
В целом, это рабочий алгоритм, но при разборе кода я обращу внимание на еще один нюанс.
Вариант реализации на typescript:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
function longestCycle(edges: number[]): number { const len = edges.length // массив для маркировки узлов // изначально заполнен значениями -1 const paths: number[] = new Array(len).fill(-1) // номер очередного узла let i = 0 // число обработанных узлов let used = 0 // самая длинная петля на текущий момент let maxLoop = -1 // номер текущего пути let pathID = 0 // последний из обработанных узлов (это тот самый нюанс) lastRES = 0; while (true) { if (paths[i] == -1) { // если узел еще не обработан // то маркируем его paths[i] = pathID used ++; lastRES = i // движемся вдоль пути в графе i = edges[i]; } else { if (paths[i] == pathID) { // узел принадлежит тому же пути => это петля, // найдем её длину let j = edges[i], len = 1; while (j != i) { j = edges[j]; len ++ } if (len > maxLoop) maxLoop = len } // выход из цикла, если узлы кончились if (used >= len) break; // следующий узел i ++; if (i >= len) i = 0 // новый путь pathID ++; } if (i == -1) { // если путь обрывается, // то можно было бы начать поиск опять с начала, // но тогда, теоретически, при большом числе обрывов // мы получим время-затраты порядка N^2. // поэтому мы будем продолжать с последнего маркированного узла i = lastRES + 1; if (i >= len) i = 0 // выход, если узлы закончились if (used >= len) break; // новый путь pathID ++ } } return maxLoop }; |
Надеюсь, вы уловили в чем заключается нюанс продолжения перебора узлов, когда мы отталкиваемся от последнего из обработанных.
