Лекция 8. Графы, обход в ширину, обход в глубину

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

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

Топологическая сортировка: определение, необходимость отсутствия циклов. Добавление фиктивной вершины, серия DFS. Определение цикла по ребру IN->IN. Время входа(tin) и выхода(tout) для вершины. Порядок топ. сорт. = порядок убывания tout. Доказательство. Сильная связность, компоненты сильной связности. Конденсация графа, сохранение достижимости, ацикличность. Поиск компонент сильной связности: прямой DFS + обратный DFS. Лемма о соотношении времён выхода двух компонент с ребром. Доказательство корректности алгоритма.

Эйлеров цикл (ор. граф). Критерий существования: слабая связность и равенство степеней входа/выхода. Док-во сильной связности. DFS по рёбрам, пометки рёбер, код. Список рёбер в порядке выхода - развёрнутый эйлеров цикл. Время работы O(V + E). Доказательство: первый возврат в стартовой вершине; в момент выписывания ребра сохраняется связность пути; обход затрагивает все вершины и рёбра графа.