Обходы: в глубину и в ширину

Граф построен, и теперь по нему надо ходить. Обход устроен проще, чем кажется, и держится на одной мысли:

Каждую вершину посещаем ровно один раз.

Для этого нужны две вещи: отметки о посещённых и запас вершин, до которых мы дошли, но ещё не обработали.

seen = [False] * (n + 1)
seen[start] = True
store = [start]

while store:
    v = взять_из(store)
    for to in adj[v]:
        if not seen[to]:
            seen[to] = True      # отмечаем СРАЗУ, при добавлении
            положить_в(store, to)

Каждая вершина попадает в запас один раз, каждое ребро просматривается дважды — по разу с каждого конца. Значит весь обход стоит $O(n + m)$ независимо от того, как устроен граф.

Отмечать надо при добавлении

Строчку seen[to] = True заманчиво перенести туда, где вершину достают из запаса. Так делать не надо: пока вершина ждёт своей очереди, до неё успеют дойти все соседи, и она попадёт в запас столько раз, сколько у неё рёбер.

Чем отличаются в глубину и в ширину

Ровно одним: чем является запас.

Всё остальное совпадает до строчки. Поэтому выбирать между ними надо не «по привычке», а по тому, что нужно: обход в ширину даёт кратчайшие расстояния, обход в глубину — нет.

Обход в глубину обычно пишут рекурсией — она короче:

def dfs(v):
    seen[v] = True
    for to in adj[v]:
        if not seen[to]:
            dfs(to)

В Python у этой красоты есть цена, о которой надо знать заранее.

Глубина рекурсии ограничена, по умолчанию тысячей. Дошли до тысячного вложенного вызова — программа падает с RecursionError.

А какой глубины бывает обход в глубину? Ровно такой, какова длина самого длинного спуска. И вот здесь легко ошибиться в оценке. Вот измеренные глубины на графах из 200 000 вершин:

Цепочка ломает рекурсию гарантированно. Но и обычный случайный граф ломает её с запасом в тридцать раз — стоит связной части стать большой, как глубина сразу измеряется десятками тысяч. Маленькой она бывает только там, где все компоненты мелкие.

Именно поэтому такое решение проходит часть тестов и падает на остальных, а размер графа сам по себе ни о чём не говорит: при двухстах тысячах вершин глубина бывает и двойкой, и двумястами тысячами.

Что с этим делать

Поднять предел вызовом sys.setrecursionlimit(300000) можно, но это опасная мера: предел интерпретатора не единственный, есть ещё настоящий стек операционной системы, и при его исчерпании программа не сообщит об ошибке, а просто аварийно завершится.

Надёжный способ — обход без рекурсии, с явным списком вместо стека вызовов:

stack = [start]
seen[start] = True
while stack:
    v = stack.pop()          # последнее добавленное — это и есть глубина
    for to in adj[v]:
        if not seen[to]:
            seen[to] = True
            stack.append(to)

Тот же алгоритм, никаких пределов. Все решения этого занятия написаны так, и вам советую то же.

От чего зависит, упадёт ли рекурсивный обход в глубину с RecursionError?

Один запуск обхода добирается до всех вершин, связанных со стартовой, — и ни до каких других. Этот набор и называется компонентой связности.

Чтобы обойти весь граф, запускаем обход из каждой ещё не посещённой вершины:

components = 0
for v in range(1, n + 1):
    if not seen[v]:
        components += 1
        обойти_от(v)

Сколько раз запустили — столько и компонент. Общая работа при этом остаётся $O(n + m)$: отметки общие для всех запусков, и ни одна вершина не обходится дважды.

Номер компоненты вместо отметки

Если вместо «посещена» записывать номер компоненты, вопрос «лежат ли две вершины в одной части графа» превращается в сравнение двух чисел. Сто тысяч таких запросов после одного обхода стоят сто тысяч сравнений, а не сто тысяч обходов.

Это общий приём: подготовить ответ один раз, а не отвечать заново на каждый вопрос. Мы уже видели его с накопленными суммами.

Граф — цепочка из 10 вершин: 1 — 2 — 3 — … — 10.

Чему равно расстояние от вершины 1 до вершины 10? Введите целое число.

Вот главное свойство обхода в ширину, ради которого его и используют.

Обход в ширину находит кратчайшие пути в невзвешенном графе.

Почему? Очередь выдаёт вершины слоями: сначала стартовая, потом все на расстоянии 1, потом все на расстоянии 2. Когда вершина впервые попадает в очередь, до неё уже найден путь, и более короткого быть не может — иначе она попала бы в очередь раньше.

Значит расстояние можно записывать прямо в момент добавления, а массив отметок и массив расстояний — это одно и то же:

dist = [-1] * (n + 1)      # -1 означает «не посещена»
dist[start] = 0
queue = deque([start])

while queue:
    v = queue.popleft()
    for to in adj[v]:
        if dist[to] == -1:
            dist[to] = dist[v] + 1
            queue.append(to)

Про deque

Очередь берите из collections.deque. У обычного списка pop(0) сдвигает все оставшиеся элементы, и обход из линейного превращается в квадратичный — на двухстах тысячах вершин это разница между «мгновенно» и «не дождётесь».

Несколько источников сразу

Если нужно расстояние до ближайшего из нескольких объектов, не надо запускать обход из каждого. Положите в очередь сразу все источники с нулевым расстоянием — слои пойдут от всех одновременно, и каждая вершина получит расстояние до ближайшего.

Один обход вместо сотни. Приём называется многоисточниковым и встречается очень часто.

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

Соседи вычисляются, а не хранятся. Вместо adj[v] — четыре смещения и проверка границ, ровно как в занятии про клетчатое поле.

Расстояния хранятся таблицей по размеру поля. Клетка $(r, c)$ — это вершина, и её удобно нумеровать числом r * m + c: тогда все массивы одномерные, а обратно координаты достаются делением с остатком.

for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
    nr, nc = r + dr, c + dc
    if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] != "#":
        ...

Проверка границ — до обращения к клетке, и по обеим осям. Напомню, что забытое nr >= 0 в Python не роняет программу, а тихо берёт клетку с другого края.

Всё остальное — тот же обход в ширину и те же кратчайшие расстояния. Лабиринт, острова, расстояние до ближайшего выхода решаются одним и тем же кодом с разными стартовыми клетками.

Отметка ставится при извлечении, а не при добавлении. Вершина попадает в очередь по разу на каждое входящее ребро. Программа даёт верный ответ, но работает в разы дольше и съедает память.

Рекурсия на длинной цепочке. Разобрано выше. Признак: часть тестов проходит, часть падает с RecursionError.

pop(0) вместо deque. Квадратичное время на ровном месте. Признак: решение верное, вердикт по времени.

Обход запущен только из первой вершины. Если граф несвязный, вершины других компонент останутся необойденными. Для задач про компоненты нужен цикл по всем вершинам.

Расстояние до недостижимой вершины. Оно не ноль и не бесконечность, а то, что просит условие, — обычно -1. Проверяйте, что недостижимые не попали в максимум или сумму.

Как проверять себя

• граф без рёбер — компонент столько же, сколько вершин;
• длинная цепочка — ловит рекурсию и квадратичную очередь;
• несвязный граф — ловит обход из одной вершины;
• лабиринт без прохода — ответ должен быть -1, а не ноль.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Почти всё занятие — один и тот же обход с разными вопросами. Напишите его один раз аккуратно, без рекурсии и с deque, и дальше меняйте только то, что считаете по дороге.

В части задач граф — это поле. Разницы в алгоритме нет, разница только в том, откуда берутся соседи.

Задача: «дан неориентированный граф из $n \le 2 \cdot 10^5$ вершин; посчитайте количество компонент связности».

Ученик написал:

n, m = map(int, input().split())
flat = list(map(int, input().split()))

adj = [[] for _ in range(n + 1)]
for i in range(0, len(flat), 2):
    adj[flat[i]].append(flat[i + 1])
    adj[flat[i + 1]].append(flat[i])

seen = [False] * (n + 1)

def dfs(v):
    seen[v] = True
    for to in adj[v]:
        if not seen[to]:
            dfs(to)

count = 0
for v in range(1, n + 1):
    if not seen[v]:
        count += 1
        dfs(v)

print(count)

Алгоритм выбран верно, граф строится правильно. Но часть тестов падает с ошибкой RecursionError, а часть проходит.

Объясните, какие именно тесты его ломают и почему, и предложите исправление.