Как алгоритм 1972 года спас наш проект и при чем тут Тарьян?
Я часто вижу в интернете дискуссии, а должен ли True-разработчик знать теорию алгоритмов и стандартные алгоритмы. Про алгоритмические собеседования вообще молчу — мнения на этот счет у всех разные, оно и понятно.
Я занимаюсь коммерческой backend разработкой уже 7 лет и в какой-то момент остро ощутил нехватку теоретических знаний. В потоке постоянной работы и дедлайнов времени на «академическое» образование не хватало.
В один момент чаша терпения переполнилась и я твердо решил «начать учиться». Выписал список тем и пошел штудировать литературу из интернета по пунктам. Тут я дошел до теории алгоритмов. Эта область компьютерной науки мне сильно понравилась и я потихоньку начал разбираться. Скажу честно, задачки давались очень тяжело, я все время ощущал, что мой мозг как будто «не настроен на волну» решения таких задач.
Тоже самое, бывало и на работе, когда тебе нужно написать какую-то функцию, а ты в голове не можешь придумать и реализовать алгоритм.
В общем увидел, что у Яндекс Практикума есть курс по алгоритмам, задумался стоит ли идти. Смотрю подробнее, 4 месяца, хм, вроде недолго. Открываю список тем — весь «джентльменский набор» по алгоритмам присутствует. Ну, думаю, ладно, надо пробовать.
Курс я успешно закончил, но история не об этом. Через некоторое время столкнулся на работе с одной проблемой. Опишу в общих чертах:
Я занимался разработкой системы электронного документооборота. Есть документ, который может менять статус. Статусов несколько и в некоторые из них документ может возвращаться по второму кругу. Например: начальнику что-то не понравилось и он отправил в статус «коррекция» — все по новой до начальника.
При этом, в каких-то статусах нужно подписание ответственного, а в каких-то нет. В БД подпись для каждого статуса только одна (хранится как закодированная строка), поэтому нужно определить, может ли документ в этом статусе подписываться несколько раз. Если да — обновлять подпись, если нет — выдавать ошибку.
Первый подход к «снаряду»
Что бы я сделал раньше? Да, ничего особенного, скорей всего написал бы «костыльное» решение, подогнанное под тест-кейсы. Просто потому что не нашел бы другого.
Но тут вдруг, смотрю я на эти статусы и понимаю — «Черт побери, да это же односторонне связный направленный граф» (Вообще графы крутая штука, любые отношения между сущностями в природе можно описать через них). А что значит «Найти повторяющиеся статусы?» — спрашиваю себя и тут же отвечаю — «Точно, найти циклы в графе». Получается нам всего лишь остается найти вершины графа, которые входят в какой-либо цикл и наша задача решена.
Решение №1. Поиск вершин, входящих в цикл графа.
Вспоминаю, что на курсе была похожая задача по поиску циклов. Не долго думая, вооружившись DFS (поиск в глубину), классическим алгоритмом обхода вершин графа, предполагаю, что для решения, нужно «запустить» поиск в глубину для каждой вершины и если нам встречается уже обработанная/пройденная вершина — значит мы попали в цикл. Собираем массив таких вершин и задачка решена. Так как я пишу на php, приведу пример реализации алгоритма на нем:
/**
* @var $arGraph array - Граф, представленный, списком смежности.
* Ключ массива - вершина, а значения смежные вершины.
*
* 2 - вершина посещена
* 1 - вершина в очереди на обработку
* 0 - вершина еще не встречалась
*/
$arVertexColors = [];
$arUpdateCodes = [];
foreach (array_keys($arGraph) as $vertex) {
$arStack = [$vertex];
$arColors = $arVertexColors;
/** Поиск в глубину */
while ($arStack) {
$currentVertex = array_pop($arStack);
$arColors[$currentVertex] = 2;
foreach ($arGraph[$currentVertex] as $neighbourVert) {
if (!$arColors[$neighbourVert]) {
$arStack[] = $neighbourVert;
$arColors[$neighbourVert] = 1;
} elseif ($arColors[$neighbourVert] == 2) { // цикл обнаружен
$arUpdateCodes[] = $neighbourVert;
}
}
}
}
return $arUpdateCodes;И вроде бы, все хорошо. Результат на выходе получается верный. Логически тоже наверно не подкопаться. Но очевидно, в этом решении что-то не так. Для каждой вершины мы запускаем поиск в глубину и посещаем все вершины заново. У такого алгоритма будет квадратичное время работы O (N2). Интуитивно, кажется, нам должно быть достаточно обойти граф один раз, чтобы найти все циклы.
Тут я вспоминаю, что есть такое понятие, как сильно связный компонент у направленного графа — это такой подграф, в котором от любой вершины v1 до любой вершины v2 есть путь как от v1 до v2, так и обратно. Такой подграф является циклом.
Я не любитель придумывать велосипеды, поэтому сразу же подумал «Наверняка какие-нибудь умные дядьки давно решили эту задачу максимально оптимальным способом». Набираю в гугле «Поиск сильно связных компонентов в направленном графе» и оказывается уже придумано 3 алгоритма решения этой задачи за линейное время:
Алгоритм Косарайю
Алгоритм Тарьяна
Алгоритм поиска компонент сильной связности с двумя стеками Дейкстры
Решение №2. Алгоритм сильно связных компонентов Тарьяна
Расскажу об алгоритме Тарьяна. Помимо описания из википедии попробую объяснить его своими словами.
Как и многие алгоритмы он основан на поиске в глубину. Мы начинаем обход каждой вершины по очереди в глубину и как только встречаем уже посещенную вершину, либо отсутствие смежных — значит мы находимся в одной из компонент сильной связности, а именно нашли корень.
Поэтому теперь нужно понять, в какой из компонент мы находимся, для этого мы как бы делаем «задний ход», восстанавливая свой прошлый путь на каждой вершине, при этом проверяем не принадлежит ли эта вершина другой компоненте. Чтобы осуществить «задний ход» на каждом шаге, мы должны сохранять наш путь в памяти, для этого заведем массив indexes и будем помечать на каком шаге пришли в вершину.
Еще надо сохранять индекс «корня» компонента связности, которому принадлежит текущая вершина, для этого используем массив lowlinks. Для хранения уже пройденных вершин воспользуемся стеком stack. Когда мы делаем «задний ход» при обнаружении корня компонента связности, извлечем из stack все вершины до корневого, тем самым добавим в массив strong_components очередную компоненту сильной связности.
На gif-ке представлена работа алгоритма. Первое число рядом с вершиной — массив indexes, второе lowlinks.
Алгоритмические задачки я решаю на python. Поэтому приведу реализацию на этом языке. При необходимости его легко можно переписать на php или на любой другой.
from collections import defaultdict
def strong_connect(vertex):
indexes[vertex], lowlinks[vertex] = len(indexes), len(indexes)
stack.append(vertex)
in_stack[vertex] = True
# Обход вершин через поиск в глубину
for neighbour_vertex in graph[vertex]:
if indexes[neighbour_vertex] == 0:
strong_connect(neighbour_vertex)
lowlinks[vertex] = min(lowlinks[vertex], lowlinks[neighbour_vertex])
elif in_stack[neighbour_vertex]:
lowlinks[vertex] = min(lowlinks[vertex], indexes[neighbour_vertex])
# Попали в корень компонента связности, извлекаем вершины потомки
if lowlinks[vertex] == indexes[vertex]:
scc = []
neighbour_vertex = None
while vertex != neighbour_vertex:
neighbour_vertex = stack.pop()
scc.append(neighbour_vertex)
in_stack[neighbour_vertex] = False
strong_components.append(scc)
if __name__ == "__main__":
# Граф списка смежности
graph = {
'A': {'B'},
'B': {'C'},
'C': {'B', 'D'},
'D': {'E'},
'E': {'F'},
'F': {'D'},
}
stack = []
indexes = defaultdict(lambda: 0)
lowlinks = defaultdict(lambda: 0)
in_stack = defaultdict(lambda: False)
scc = []
strong_components = []
# Обход оставшихся вершин
for vertex in graph:
if indexes[vertex] == 0:
strong_connect(vertex)
print(strong_components)Во время поиска описания работы алгоритма, мне было недостаточно тех материалов, которые есть в интернете. Их было буквально штук 10, которые объясняли в общих чертах. Возможно, кому-то поможет мое объяснение и пример кода :)
Итоги
В сухом остатке имеем следующее: наш граф статусов мы представим в виде списка смежности и «скормим» его алгоритму Тарьяна. На выходе получаем самое оптимальное решение нашей задачи за линейное время исполнения O (V + E), где V — это количество вершин графа, а E — количество ребер.
Я описал свой опыт полезности знания теории алгоритмов и применение их на практики. Даже просто знание каких-то основ, как в моем случае, может сильно сэкономить ваше время как в работе, так и в повседневной жизни. Поэтому вопрос «нужности» таких знаний, для меня, кажется, стал риторическим :)
