# конспект · шаг 8 из 8
Конспект: обход в глубину
Понятия
Обход в глубину (DFS) - обход дерева плюс массив пометок; пометка ставится при ВХОДЕ.
Цена O(V + E) на списках смежности и O(V²) на матрице.
Внешний цикл по всем вершинам: число запусков = число компонент связности.
Времена tin / tout - один счётчик, растёт и на входе, и на выходе (всего 2V меток).
Теорема о скобках - отрезки [tin, tout] либо вложены, либо не пересекаются.
Следствие: u - предок v ⇔ tin[u] < tin[v] и tout[v] < tout[u] (проверка O(1)).
Цвета: белая - не тронута, СЕРАЯ - на текущем пути (вошли, не вышли), чёрная - закончена.
Эйлеров цикл - проходит каждое ребро ровно раз; есть, когда граф с рёбрами связен и все степени
чётны (ориентированный - вход равен выходу). Эйлеров путь - нечётных вершин ровно две, они концы.
Алгоритм Хирхольцера - стек неиспользованных рёбер, вершина уходит в ответ при отступлении;
O(V + E).
Что унести
Классификация ребра u → v по цвету v:
цвет v |
вид ребра | значит |
|---|---|---|
| белая | древесное | по нему спускаемся |
| СЕРАЯ | обратное | цикл |
чёрная, tin[u] < tin[v] |
прямое | потомок, до которого дошли другим путём |
чёрная, tin[u] > tin[v] |
перекрёстное | другая ветвь |
ориентированный граф ацикличен ⇔ обход не нашёл обратного ребра
Главная ловушка: искать цикл по visited. Ребро в ЧЁРНУЮ вершину циклом не является; на графе
0→1, 0→2, 1→2 такой код объявляет цикл, которого нет. Тестировать детектор цикла надо в первую
очередь на графах БЕЗ циклов.
В неориентированном графе бывают только древесные и обратные рёбра; ребро в родителя пропускают, а при кратных рёбрах - по номеру РЕБРА, а не вершины.
Реализация:
| способ | когда |
|---|---|
| рекурсия | разовый скрипт, граф заведомо неглубокий |
| явный стек (простой) | нужен только охват; порядок зеркальный, нужна проверка при извлечении |
| явный стек с индексом соседа | нужны tout и действие «при выходе» - все алгоритмы дальше |
| очередь вместо стека | обход в ШИРИНУ: кратчайшие пути в невзвешенном графе |
Пределы: Python - около тысячи вложенных вызовов, компилируемый код - около ста тысяч кадров при стеке в 8 МБ. Память обхода задаёт форма графа: в глубину - длина пути, в ширину - ширина уровня.
Последовательность де Брёйна - эйлеров цикл в графе слов длины k − 1: все 2^k кодов за
2^k + k − 1 нажатий (для k = 4 - 19 вместо 64).
Для эйлерова цикла мало чётных степеней - нужна ещё связность: два отдельных треугольника имеют все степени по два, а единого цикла нет.
Куда это ведёт
Обратный порядок выхода из вершин даёт топологическую сортировку, серый цвет - поиск циклов,
tin плюс «минимально достижимое время» - мосты и точки сочленения. Следующая глава - первые два.
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий