Алгоритмы поиска
Алгоритмы поиска в ширину и в глубину в направленных графах почти не отличаются от аналогичных алгоритмов для ненаправленных графов. В этом разделе мы займемся BFS.
Алгоритм начинает с узла s, определяет первый уровень из всех узлов, к которым ведет ребро из s, затем определяет второй уровень из всех узлов, к которым ведут ребра из узлов первого уровня, и т. д.
Важно понимать, что именно вычисляет направленная версия 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.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу