Поиск в глубину
Среда, 06 ноября 2013
ФМЛ 239, Актовый зал
Поиск в глубину: поиск пути, восстановление пути, хранение графа. Деревья, циклы, компоненты связности.
Задача 1: за O(E) разбить ребра неорграф на набор циклов и остовный лес.
Задача 2: поиск цикла, проходящего через данную вершину/ребро
Задача 3: сильная связность, конденсация графа.