Алгоритмы и структуры данных 5. Графы, DFS, Topological Sort

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

На 1:18:45 картинка зависла. С последних 6 минут остался только звук. Приносим свои извинения. Пример работы алгоритма Косарайю можете посмотреть в записях прошлого года или в статье на habr. Ссылки:
АиСД 2021:    • Алгоритмы и структуры данных 5. Сильн...  
Хабр: https://habr.com/ru/post/537290/

Лекция прочитана 3 марта 2022 года
Лектор: Степанов Илья Даниилович
Оператор: Ирина Жулябина
Монтаж: Жильцов Игорь

0:00 - Основные определения
18:55 - Хранение графов в памяти компьютера
29:08 - DFS
36:26 - Лемма о белых путях
44:32 - Следствие. Поиск достижимых из S вершин
46:27 - Следствие'. Обнаружение цикла, достижимого из S
55:19 - Парочка замечаний
59:12 - Топологическая сортировка
1:01:33 - Пример топсорта
1:03:30 - Код топсорта
1:04:56 - Корректность топсорта
1:11:06 - Задача. Найти кол-во путей в DAG
1:15:09 - Алгоритм Косарайю
1:18:27 - Радио-пример