Тренировки по алгоритмам 3.0. Лекция 6: «Обход графов в ширину»

Опубликовано 6 марта 2023, 17:37

Домашние задания:
— для дивизиона А: contest.yandex.ru/contest/4546...
— для дивизиона В: contest.yandex.ru/contest/4546...

Подробнее о Тренировках по алгоритмам 3.0: yandex.ru/yaintern/algorithm-t...

0:00 заставка
4:40 начало

5:37 обход в ширину - базовая идея
11:50 восстановление пути в неориентированном графе
12:47 используя сохранение вершин
21:20 используя очередь
25:33 несколько начал и концов
29:42 обход на графе
32:37 восстановление пути в ориентированном графе
35:00 вопросы
39:54 вершины и ребра на кратчайших путях

48:30 кратчайший путь в большом графе
53:21 вопросы
57:37 граф состояний

1:06:56 кратчайший путь на 0-1 графе
1:15:52 кратчайший путь на 0-k графе

1:21:47 вопросы
1:29:48 организационные моменты контеста