Видеозаписи лекций ЛКШ
Алгоритм DFS. Классификации ребер. Время входа и выхода из вершины.
Лектор: Олег Пестов
2008.Август
Параллель B'
Поиск в глубину
Описание и реализация алгоритма. Выделение компонент связности в неориентированном графе. Сложность DFS. Остовные деревья. Классификация ребер.
Остовные деревья. Классификация ребер. Поиск цикла.
Алгоритм DFS. Классификации ребер. Время входа и выхода из вершины.
Предки и потомки.
Белые, серые и черные вершины. Поиск цикла.
Топологическая сортировка.
Компоненты сильной связности.
Конденсация графа.
Точки сочленения. Мосты.
Реализация алгоритма поиска точек сочленения и мостов.
Элеров путь и эйлеров цикл.