Графы, обход в ширину, обход в глубину
Алгоритмы и структуры данных, часть 2


Что: Лекция
Когда: Суббота, 31 марта 2018, 14:30–16:05
Где: НГУ, ауд. 2128
Слайды: algorithms_2_lecture_310318.pdf

Описание

Ориентированные графы. Задача о достижимом множестве. Представления графа. Список рёбер, матрица, списки исходящих/входящих. Память и время работы общих операций для этих структур. Статический граф: плотно упакованные списки исходящих. Обход в ширину (BFS). Случай единичных весов. Слои вершин по расстоянию, рекуррентное соотношение. Построение слоёв один за другим. Хранение двух соседних слоёв в очереди. Время работы O(V + E).

Обход в глубину, пометки вершин (NONE/IN/OUT). Классификация вершин по пометкам в процессе обхода. Отсутствие OUT->NONE рёбер, лемма о NONE-пути, док-во корректности алгоритма. Время работы O(V+E). Обход части графа за её размер.

Видео