Алгоритмы и структуры данных 4. Простые алгоритмы на графах (DFS)

Описание

00:00 - Введение
00:25 - Определение графа
04:07 - DFS (depth-first search)
08:50 - Псевдокод
12:25 - Лемма о белых путях
22:51 - Следствия
31:03 - DAG, топологическая сортировка
43:32 - сильная связность
47:52 - Алгоритм Косарайю
54:39 - Доказательство корректности
1:05:44 - Следствие
1:09:29 - Задача 2SAT

Дата лекции: 28.02.24
Лектор: Степанов Илья Данилович

Оператор: Евтушенко Иван
Монтажёр: Зинин Роман

Плейлист: https://youtube.com/playlist?list=PL4_hYwCyhAvanbmRgXMbzOdDPt2ZSb3ht&si=58MlSfrBSw0b695E