Алгоритмы (базовый поток) 7. TopSort, SSC, Эйлеровы графы

Дата лекции: 30.03.23
Лектор: Ибрагимов Б. Л.

00:00:00 Начало
00:01:12 Задачи топологической сортировки
00:03:45 Топологическая сортировка
00:06:55 Идея топологической сортировки
00:11:00 Псевдокод алгоритма Тарьяна топологической сортировки
00:15:30 Корректность
00:19:14 Время работы алгоритма Тарьяна
00:20:58 Компоненты сильной связности (SSC)
00:24:10 Конденсация графа
00:41:15 Идея алгоритма поиска SSC
00:46:33 Псевдокод алгоритма Косарайю поиска SSC + время работы
00:47:44 Корректность
00:55:02 Эйлеровы графы
00:56:34 Критерий эйлеровости для неорграфа
01:00:27 Критерий полуэйлеровости для неорграфа
01:01:40 Критерии (полу)эйлеровости для орграфа
01:03:41 Идея алгоритма поиска эйлерова цикла
01:05:37 Псевдокод алгоритма поиска эйлерова цикла

Съемка: Казанцева Таня
Монтаж: Степашин Егор