Тренировки по алгоритмам 3.0. Лекция 5: «Обход графов в глубину»
Вставка
- Опубліковано 28 лют 2023
- Подробнее о Тренировках по алгоритмам 3.0: yandex.ru/yaintern/algorithm-...
Домашнее задание станет доступно после завершения лекции:
- для дивизиона А: contest.yandex.ru/contest/45469
- для дивизиона В: contest.yandex.ru/contest/45468
Очень классная лекция, доступно, понятно, многим спикерам такому бы поучиться. Приятная и грамотная речь, разбавленная в нужных местах юмором.
Спасибо 👍
4:20 - Начало
4:50 - 1. Обход в глубину и связность
15:02 - Список смежности
19:17 - Выход из лабиринта
25:05 - Компоненты связности
34:15 (ответы на вопросы), 40:02 (начало) - 2. Поиск циклов
52:20 - Двудольные графы
1:05:57 - 3. Топологическая сортировка
1:28:17 - Лампа
1:28:19 - Конец
1:22:35 - ответы на вопросы
крутой мужик, прямо объясняет все понятно стало 👍
кажется забыли эту лекцию добавить в плэйлист с лекциями
Спасибо за лекцию. Но так не хватает примера кода, особенно если пришел не из IT. В изучении наук примеры полезнее правил.
Как грамотно осуществить мемоизацию, если нужно восстановить все возможные пути от А до Б в ориент графе? Пример на литкоде - All Paths From Source to Target. Чтобы когда приходить в уже посещенную вершину, то просто прибавлять из memo путь, который будет после вплоть до Б.
Backtracking - положил текущую вершину в хранилище текущего пути, вызвал dfs, убрал вершину из хранилища.