Алгоритмы поиска

Алгоритмы поиска в ширину и в глубину в направленных графах почти не отличаются от аналогичных алгоритмов для ненаправленных графов. В этом разделе мы займемся BFS.

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

При таком подходе узлы будут обнаруживаться уровень за уровнем в ходе распространения поиска от s,  а уровень j будет состоять из узлов, для которых кратчайший путь из s содержит ровно j ребер. Как и в ненаправленном графе, этот алгоритм выполняет не более чем постоянный объем работы для каждого узла и ребра и поэтому работает за время O(m + n).

Важно понимать, что именно вычисляет направленная версия BFS. В направленных графах путь от узла s к t может существовать даже в том случае, если путь от t к s не существует; а направленная версия BFS вычисляет множество всех узлов t, обладающих тем свойством, что от s существует путь к t. От таких узлов могут существовать пути обратно к s, а могут и не существовать.

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

В этом случае также используется рекурсивная процедура, которая пытается исследовать граф на максимально возможную глубину (на этот раз только по ребрам с соответствующим направлением). Когда DFS находится в узле u, он по порядку запускает рекурсивный поиск в глубину для каждого узла, к которому ведет ребро из u.

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

Это можно легко сделать, определив новый направленный граф Grev, который получается из G простым изменением направления каждого ребра. После этого алгоритм BFS или DFS применяется к Grev; путь из s к узлу существует в Grev в том, и только в том случае, если в G существует путь из него в s.