Где применяется
1. Задача
В прошлом уроке BFS обходил граф кольцами: старт, потом все узлы на шаг дальше, потом на два шага, и всё это через очередь. Его берут, когда сначала нужны ближайшие узлы.
Поиск в глубину (depth-first search, DFS) обходит тот же граф по-другому. Ты выбираешь один путь и идёшь по нему, пока не упрёшься в тупик. Потом возвращаешься к последней развилке и пробуешь следующую ветку. Ты так же посещаешь каждый достижимый узел, только в другом порядке.
Задачи те же, что у BFS: дойти до каждого узла, до которого можно добраться от старта, и не ходить по кругу, когда связи замыкаются. Этот урок отвечает на вопрос: в каком порядке выходят узлы, если идти вглубь, а не расходиться кольцами.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на граф, где нужно пройти каждый путь или закончить всю ветку, прежде чем идти дальше. Поиск в глубину уходит как можно глубже, отмечает посещённые узлы и возвращается, чтобы попробовать следующего соседа.
В графе нет циклов, поэтому поиску в глубину не нужно множество visited, а узел добавляешь в путь по дороге вниз и убираешь на обратном пути.
Храни каждую дорогу в обе стороны с пометкой её настоящего направления, иди в глубину от 0 и считай дороги, которые смотрят от 0.
Иди в глубину по дереву подчинения от главы и возвращай самую большую сумму времени оповещения по какой-нибудь ветке.
Каждое равенство это ребро с весом в обе стороны, а поиск в глубину от одной переменной перемножает веса, пока не дойдёт до другой.