Лекция 8. Графы, обход в ширину, обход в глубину (Алгоритмы и структуры данных, часть 2)

Ориентированные графы. Задача о достижимом множестве. Представления графа. Список рёбер, матрица, списки исходящих/входящих. Память и время работы общих операций для этих структур. Статический граф: плотно упакованные списки исходящих. Обход в ширину (BFS). Случай единичных весов. Слои вершин по расстоянию, рекуррентное соотношение. Построение слоёв один за другим. Хранение двух соседних слоёв в очереди. Время работы O(V E). Обход в глубину, пометки вершин (NONE/IN/OUT). Классификация вершин по пометкам в процессе обхода. Отсутствие OUT-NONE рёбер, лемма о NONE-пути, док-во корректности алгоритма. Время работы O(V E). Обход части графа за её размер. Лекция №8 в курсе “Алгоритмы и структуры данных, часть 2“, весна 2018 (Новосибирск) Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов Страница лекции на сайте CS центра: Все видео курса по порядку: