3. Поиск в глубину

Применение поиска в глубину

Поиск в глубину может использоваться для следующих целей:

1. Выявление компонент связности, их количества и размера.
Пример применения:
Разбор задачи 1309. Считая облака (связи между вершинами графа заданы явно)
Разбор задачи 1269. Саванна (связи между вершинами графа заданы неявно)

2. Обработка ациклических ориентированных графов, деревьев.
Разбор задачи 1384. Производство деталей (связи между вершинами графа заданы явно)
Разбор задачи 1251. Шкатулки (связи между вершинами графа заданы неявно)

3. Выявление циклов в ориентированных графах, топологическая сортировка.
Алгоритм топологической сортировки

4. Нахождение произвольного пути, не обязательно кратчайшего, между двумя вершинами в графе.

5. Поиск мостов и компонентов сильной связности

Термины:
Компонента связности графа — некоторое подмножество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.
Мост – ребро, удаление которого увеличивает количество компонент связности в графе.
Компонента сильной связности графа — максимальное множество вершин ориентированного графа такое, что для любых двух вершин из этого множества существует путь как из первой во вторую, так и из второй в первую.