Алгоритмы поиска
Важно понимать, что именно вычисляет направленная версия BFS. В направ- ленных графах путь от узла s к t может существовать даже в том случае, если путь от t к s не существует; а направленная версия BFS вычисляет множество всех узлов t, обладающих тем свойством, что от 5 существует путь к t.
От таких узлов могут существовать пути обратно к s, а могут и не существовать.Для поиска в глубину тоже существует естественная аналогия, которая вы- полняется за линейное время и вычисляет то же множество узлов. В этом случае также используется рекурсивная процедура, которая пытается исследовать граф на максимально возможную глубину (на этот раз только по ребрам с соответствующим направлением). Когда DFS находится в узле и, он по порядку запускает рекурсив- ный поиск в глубину для каждого узла, к которому ведет ребро из u.
Допустим, для заданного узла s требуется получить множество узлов, от кото- рых существуют пути к s (вместо узлов, к которым ведут пути из s). Это можно легко сделать, определив новый направленный граф Grev, который получается из G простым изменением направления каждого ребра. После этого алгоритм BFS или DFS применяется к Grev; путь из s к узлу существует в Grev в том, и только в том случае, если в G существует путь из него в s.
Еще по теме Алгоритмы поиска:
- Поиск смысла жизни – это поиск бессмертия!
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- Алгоритм исцеления:
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- ПОИСК ИНФОРМАЦИОННЫЙ
- ЧАСТЬ 2 В ПОИСКАХ УТРАЧЕННОГО «Я»
- ТЕОРИЯ ПОИСКА СМЫСЛА ЖИЗНЕННОГО
- Направление поиска работы
- Направление поиска работы
- 3.11.6. Поиск на ощупь