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

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

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

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Алгоритмы поиска:

  1. Поиск смысла жизни – это поиск бессмертия!
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  9. Алгоритм обработки результатов.
  10. 2. Специфика и алгоритмы работы с источниками.
  11. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  12. ПОИСК ИНФОРМАЦИОННЫЙ
  13. ЧАСТЬ 2 В ПОИСКАХ УТРАЧЕННОГО «Я»
  14. ТЕОРИЯ ПОИСКА СМЫСЛА ЖИЗНЕННОГО
  15. Направление поиска работы
  16. Направление поиска работы
  17. 3.11.6. Поиск на ощупь