mercury13_kiev


Это не баг, это фича!


Previous Entry Share Next Entry
Водка «Синяк», ответ
mercury13_kiev

Текст задачи

Распишем, каков приоритет всех узлов, связанных с данным запасом. Ничего не напоминает?

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

Более строгое доказательство. Сначала рекурсивно правая ветвь. Потом всё, что остаётся, из левой. Наконец, сама вершина.

Алгоритм таков. Сначала рекурсивно отмечаем белым всех предков, прямых и непрямых. Затем производим поиск в глубину (приоритет выбора дорог — обратный, от правых к левым). На выходе из узла модифицируем наши вычисленные настройки.

Применение к жизни. Поиск в глубину не любят на «очень связных» графах: памяти отъест примерно столько же, сколько вершин в графе. Однако на разного рода орграфах и деревьях поиск в глубину вполне себе действует.

Кроме того, в поиске в глубину бывает важен порядок входа или выхода. Так, алгоритм Косарайю вычисления компонент сильной связности орграфа работает так: проводим поиск в глубину против дуг и запоминаем порядок входа. Проводим поиск в глубину уже на обычном графе в порядке, обратном запомненному.


?

Log in

No account? Create an account