Семинар 10. Остовные деревья, сжатие компонент (Алгоритмы и структуры данных, часть 2)

Построение графа по запросам на достижимость и недостижимость. Проверка M достижимостей в (N,M)-графе за O(M N). Сжатие компонент сильной связности. Динамическое программирование в порядке топ. сорт. Использование битовых масок. Сокращение затрат памяти.
Найти мин. мн-во вершин, достижимых из любой вершины после удаления любого ребра. Мосты и компоненты двусвязности. Сжатие компонент, получение дерева. Мн-во висячих вершин = ответ. Количество ответов.
Задача о минимальном остовном дереве (МОД). Лес хороший, если дополняется до МОД. Разрез в графе. Лемма о разрезе (сохранение хорошести при добавлении ребра). Фундаментальные циклы графа относительно остовного дерева.
Алгоритм Прима. Множество посещённых вершин B. Добавляется мин. ребро в разрезе B | (V\B). Реализация по аналогии с алгоритмом Дейкстры, хранение мин. ребра для серых вершин. Время работы O(E log V).
Алгоритм Краскала. Храним лес, добавляем мин. ребро между деревьями. Сортировка рёбер, добавление по одному. Использование сист. неперес. мн-в для хранения компонент связности. Время работы O(E log V).
Семинар №10 в курсе "Алгоритмы и структуры данных, часть 2", весна 2018 (Новосибирск)
Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов
Страница лекции на сайте CS центра: https://bit.ly/2JACpB8
Все видео курса по порядку: https://goo.gl/b8KQcs

Видео Семинар 10. Остовные деревья, сжатие компонент (Алгоритмы и структуры данных, часть 2) канала Computer Science Center