🔴 Сложный ⏱️ 55 минут

Обход графов (DFS, BFS)

📋 Содержание урока

Обход графов (DFS, BFS) 🧭

Открой LinkedIn и посмотри на подпись под профилем малознакомого человека: «у вас 3 общих связи» или «связаны через 2 рукопожатия». Кто-то посчитал это число — и посчитал его не перебором всех возможных цепочек знакомств (их триллионы), а конкретным алгоритмом, который аккуратно расширяется от тебя волнами: сначала твои прямые друзья, потом друзья друзей, потом друзья друзей друзей — пока не наткнётся на нужного человека. Этот алгоритм называется обход в ширину, BFS, и его ответ — не приблизительная оценка, а точное минимальное число рёбер на пути между двумя вершинами графа.

В прошлых двух уроках ты разобрался, что такое граф формально ($G = (V, E)$, вершины и рёбра) и как его хранить в памяти компьютера — матрицей смежности или списком смежности. Но представление графа — это только структура данных, пассивный склад информации о том, кто с кем связан. Сам по себе список смежности не умеет отвечать на вопросы вроде «а можно ли добраться от вершины A до вершины B вообще» или «а какое расстояние между ними в рёбрах». Чтобы граф «ожил» и начал отвечать на такие вопросы, нужен алгоритм, который умеет по нему двигаться — методично посещать вершины одну за другой, не теряя нить и не блуждая по кругу. Это и есть обход графа.

Ты уже встречал похожую идею в уроках про деревья — обход в глубину и обход в ширину дерева. Может показаться, что для произвольного графа достаточно взять готовые алгоритмы с деревьев и ничего не менять. Это почти правда, но есть одна деталь, из-за которой «почти» здесь принципиально: в дереве нет циклов, а значит, спускаясь вниз от корня, ты физически не можешь вернуться в уже посещённый узел. В произвольном графе циклы — обычное дело (представь: ты дружишь с Аней, Аня дружит с Борей, а Боря снова дружит с тобой). Без специального механизма, который «помнит», где ты уже был, алгоритм обхода графа с циклом будет бегать по этому циклу бесконечно и никогда не завершится. Эта одна деталь — метка посещённых вершин — и есть главное, что отличает обход графа от обхода дерева, и именно ей будет посвящена значительная часть этого урока.

За обходом графов стоит не абстрактная красота, а конкретная вычислительная мощь, на которой держится половина повседневного интернета. BFS считает степени разделения в социальной сети и находит кратчайший маршрут в GPS-навигаторе, где граф — это перекрёстки и улицы без весов (или с одинаковыми весами). DFS обнаруживает изолированные кластеры в графе знаний, проверяет, не образует ли граф зависимостей задач порочный круг, и лежит в основе алгоритмов топологической сортировки, к которой ты перейдёшь в следующем уроке. Оба алгоритма работают за время, пропорциональное размеру графа — $O(V + E)$, где $V$ — число вершин, $E$ — число рёбер, — и это одна из самых элегантных гарантий эффективности во всей алгоритмике: ты не тратишь ни одной лишней операции сверх того, что нужно просто один раз взглянуть на каждую вершину и каждое ребро.

История: откуда взялись эти идеи

Идея систематического перебора всех путей в графе восходит ещё к XIX веку — французский математик Гастон Тарри в 1895 году описал правило обхода лабиринта, которое по сути представляет собой алгоритм поиска в глубину: иди по новому проходу, если он есть; если все проходы из текущей точки уже пройдены, вернись назад на шаг и попробуй другой вариант. Похожий принцип, как принято считать, ещё раньше сформулировал французский инженер Шарль Пьер Тремо для решения задачи о выходе из лабиринта: правило, дошедшее до нас через сборник Эдуарда Люка «Математические развлечения» (1882), предписывало помечать пройденные коридоры — прямой прообраз современной метки посещённых вершин. Забавно, что задача навигации в физическом лабиринте и задача обхода абстрактного графа знаний в базе данных решаются буквально одним и тем же алгоритмом спустя полтора века.

Формализация DFS и BFS как алгоритмов на графах в современном виде произошла в середине XX века вместе с бурным развитием теории графов и информатики. Систематическое исследование обхода в ширину как метода поиска кратчайшего пути в невзвешенном графе связывают с работами Эдварда Мура (1959) и независимо Клода Шеннона — тем самым Шенноном, который считается отцом теории информации; Шеннон интересовался задачей обхода лабиринта механической мышью «Тесей», и алгоритм, которым эта мышь находила выход, по сути был BFS. К 1960–70-м годам, когда информатика оформилась в самостоятельную дисциплину, DFS и BFS вошли в стандартный набор инструментов, на котором строится буквально всё остальное: поиск компонент связности, обнаружение циклов, топологическая сортировка, алгоритмы кратчайших путей вроде Дейкстры (BFS — его частный случай для графа с единичными весами).

Сегодня эти алгоритмы работают на масштабах, которые их изобретателям было бы сложно вообразить. Когда LinkedIn вычисляет «связь третьей степени», под капотом крутится BFS на графе из сотен миллионов вершин. Когда поисковый робот Google обходит веб-страницы, переходя по ссылкам, он выполняет вариант DFS или BFS на графе интернета. Идея полуторавековой давности — «иди вперёд, если можешь, иначе возвращайся назад; и не заходи дважды в одно и то же место» — оказалась одной из самых долгоживущих во всей информатике именно потому, что она предельно проста и при этом абсолютно универсальна.

Обход в глубину (DFS) на графах и пометка посещённых вершин

Интуиция: иди вперёд, пока можешь, потом возвращайся

Представь, что ты исследуешь незнакомую пещерную систему с фонариком и мелом. Ты заходишь в первый попавшийся проход и идёшь по нему, пока не упрёшься в развилку или тупик. На развилке выбираешь любой ещё не пройденный проход и снова идёшь до конца. Когда упираешься в тупик (или во все проходы из текущей точки, которые уже помечены мелом как пройденные), ты разворачиваешься и идёшь назад — к последней развилке, где оставался непройденный вариант, и пробуешь его. Это и есть обход в глубину: максимально быстро зайти как можно дальше в одном направлении, а к остальным вариантам возвращаться только когда текущее направление исчерпано.

Ключевое слово здесь — «мелом»: без пометок ты рано или поздно зайдёшь в проход, который уже проходил, и, если в пещере есть кольцевой коридор (цикл), можешь бродить по нему вечно, каждый раз считая его «новым». В дереве такой проблемы не было бы в принципе: спускаясь от корня вниз по ветвям, физически невозможно вернуться в уже посещённый узел, потому что в дереве нет обратных рёбер, которые замыкали бы путь в кольцо. У произвольного графа таких гарантий нет — и поэтому явная метка посещённых вершин на графах не факультативная оптимизация, а обязательное условие корректности алгоритма.

Алгоритм

Обход в глубину (DFS), рекурсивная версия. Дан граф $G = (V, E)$ в виде списка смежности и стартовая вершина $s$. Заводим множество visited (изначально пустое). Функция dfs(v):

Если $v$ уже в visited — вернуться (эту вершину уже обработали).

Добавить $v$ в visited (пометить как посещённую) и обработать $v$ (например, вывести или сохранить в результат).

Для каждого соседа $u$ вершины $v$ из списка смежности: рекурсивно вызвать dfs(u).

Запуск: dfs(s). Рекурсия неявно использует стек вызовов — тот же механизм, что и явный стек в итеративной версии DFS на деревьях из урока 253. Итеративная версия использует явный стек: положить $s$ в стек; пока стек не пуст — извлечь вершину $v$ с вершины стека, если она не посещена — пометить как посещённую, обработать и положить в стек всех её непосещённых соседей.

Обе версии — рекурсивная и итеративная — обходят граф в одном и том же логическом порядке «вглубь, потом назад», хотя конкретный порядок посещения соседей может немного отличаться из-за того, что стек разворачивает порядок добавления. На практике рекурсивную версию пишут чаще из-за читаемости, а итеративную — когда граф настолько велик, что глубина рекурсии рискует превысить лимит стека вызовов языка программирования (в Python это типично уже на графах с несколькими тысячами последовательно связанных вершин).

Разбор примеров

Пример 1 (лёгкий). Граф-«путь» без циклов: вершины 1–2–3–4, рёбра $(1,2), (2,3), (3,4)$. Выполнить DFS от вершины 1 и убедиться, что метка посещённых здесь не критична (граф ацикличен), но всё равно нужна для корректной остановки.

graph = {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}

def dfs_recursive(graph, v, visited, order):
    visited.add(v)
    order.append(v)
    for u in graph[v]:
        if u not in visited:
            dfs_recursive(graph, u, visited, order)
    return order

visited = set()
order = dfs_recursive(graph, 1, visited, [])
print(order)  # [1, 2, 3, 4]

Порядок обхода здесь предсказуем и совпадает с обычным линейным проходом: от 1 идём в 2 (единственный сосед), из 2 могли бы вернуться в 1, но она уже посещена — идём в 3, из 3 аналогично идём в 4, из 4 сосед 3 уже посещён — рекурсия сворачивается. Даже на этом простом ациклическом графе метка посещённых вершин предотвращает бесполезный повторный обход: без проверки if u not in visited из вершины 2 алгоритм попытался бы снова зайти в 1, из 1 — снова в 2, и так далее без остановки.

Пример 2 (средний, граф с циклом). Вершины 1, 2, 3, 4 образуют цикл: рёбра $(1,2), (2,3), (3,4), (4,1)$, плюс «хвост» — ребро $(2, 5)$. Показать, что без пометки посещённых вершин обход зацикливается, и как метка это исправляет.

graph = {1: [2, 4], 2: [1, 3, 5], 3: [2, 4], 4: [3, 1], 5: [2]}

# ПРАВИЛЬНО: с меткой посещённых
def dfs(graph, start):
    visited = set()
    stack = [start]
    order = []
    while stack:
        v = stack.pop()
        if v in visited:
            continue
        visited.add(v)
        order.append(v)
        for u in graph[v]:
            if u not in visited:
                stack.append(u)
    return order

print(dfs(graph, 1))  # [1, 4, 3, 2, 5] (конкретный порядок зависит от порядка соседей)

Обрати внимание на цикл $1 \to 2 \to 3 \to 4 \to 1$: без строки visited.add(v) и проверки if v in visited: continue алгоритм, дойдя из 4 обратно до 1, положил бы в стек уже обработанную вершину 1 снова, из неё — снова 2, снова 3, снова 4, и так бесконечно, ни разу не дойдя до вершины 5. Метка посещённых — не украшение алгоритма, а единственное, что превращает потенциально бесконечный процесс в гарантированно конечный: каждая вершина попадает в visited не более одного раза, значит, каждая вершина обрабатывается не более одного раза, и алгоритм обязан остановиться, обработав не больше $|V|$ вершин.

Пример 3 (сложный, ML — обход графа знаний). Граф знаний содержит сущности-вершины и связи-рёбра: "Python" → "Django", "Python" → "Flask", "Django" → "ORM", "Flask" → "ORM", "ORM" → "SQL", "SQL" → "Python" (цикл — SQL-запросы пишутся на Python-обёртках, которые снова упоминают Python). Найти все сущности, достижимые из "Python" через DFS.

knowledge_graph = {
    "Python": ["Django", "Flask"],
    "Django": ["ORM"],
    "Flask": ["ORM"],
    "ORM": ["SQL"],
    "SQL": ["Python"],
}

def reachable_entities(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                stack.append(neighbor)
    return visited

print(reachable_entities(knowledge_graph, "Python"))
# {'Python', 'Django', 'Flask', 'ORM', 'SQL'}

Здесь цикл SQL → Python замыкает граф в кольцо, и без метки visited обход застрял бы, бесконечно циркулируя по маршруту Python → Django → ORM → SQL → Python → .... С меткой алгоритм честно проходит по всем пяти сущностям ровно один раз и корректно завершается, вернув полное множество концепций, связанных с «Python» в этом фрагменте графа знаний. Именно так системы вроде поисковых движков со встроенными графами знаний (тот же Google Knowledge Graph) вычисляют, какие темы «связаны» с исходным запросом, прежде чем показать блок «люди также ищут».

Почему это важно

Разница между обходом дерева и обходом графа — не техническая мелочь для перфекционистов, а вопрос корректности программы. Дерево из урока 253 можно было обходить рекурсивно без единой мысли о повторных посещениях, потому что структура дерева сама гарантирует отсутствие циклов. Как только ты переходишь от деревьев к произвольным графам — социальным сетям, картам дорог, графам знаний, — эта гарантия исчезает, и «дерево-мышление» без метки посещённых вершин превращается в готовую бесконечную петлю. Привычка сначала спросить себя «может ли в этом графе быть цикл?» и, если да или если не уверен, — сразу заводить множество visited, экономит часы отладки зависшей программы.

Обход в ширину (BFS) на графах и кратчайший путь по числу рёбер

Интуиция: расходящиеся волны, а не один длинный маршрут

Если DFS — это исследователь, ныряющий в один проход как можно глубже, то BFS — это волна, расходящаяся по воде от точки, куда бросили камень. Сначала вода касается точек на расстоянии одного «шага» от центра, затем — двух шагов, затем трёх, и так далее, слой за слоем, никогда не перескакивая через уровень. В графе роль «слоёв» играют вершины на одинаковом минимальном расстоянии (в рёбрах) от стартовой: сначала обрабатываются все прямые соседи старта, потом все соседи соседей, которые ещё не были обработаны, потом их соседи, и так далее.

Это и есть источник главного практического свойства BFS: он находит кратчайший путь по числу рёбер в невзвешенном графе гарантированно, а не приблизительно. Раз BFS обрабатывает вершины строго по возрастанию расстояния от старта — сначала все на расстоянии 1, потом все на расстоянии 2, — то первый же раз, когда алгоритм добирается до конкретной целевой вершины, это происходит на минимально возможном расстоянии. DFS такой гарантии не даёт в принципе: он может по чистой случайности сначала нырнуть в длинный обходной путь и найти целевую вершину только после десятков лишних шагов, хотя более короткий путь существовал.

Алгоритм

Обход в ширину (BFS). Дан граф $G = (V, E)$ в виде списка смежности и стартовая вершина $s$. Заводим очередь queue (структура FIFO — «первым пришёл, первым вышел», см. урок 253) и множество visited.

Положить $s$ в очередь и сразу пометить как посещённую (dist[s] = 0).

Пока очередь не пуста: извлечь вершину $v$ из начала очереди, обработать её.

Для каждого соседа $u$ вершины $v$: если $u$ ещё не посещена — пометить её как посещённую в момент добавления в очередь (а не в момент извлечения!), присвоить dist[u] = dist[v] + 1 и добавить $u$ в конец очереди.

Повторять шаг 2–3, пока очередь не опустеет.

После завершения dist[v] для каждой достижимой из $s$ вершины $v$ — это точная длина кратчайшего пути от $s$ до $v$ в числе рёбер.

Момент пометки вершины посещённой в BFS заслуживает отдельного внимания, потому что здесь легко ошибиться: правильно помечать вершину как visited сразу при добавлении в очередь, а не когда она из очереди извлекается. Если пометить только при извлечении, одна и та же вершина может успеть попасть в очередь несколько раз (её могли добавить туда сразу несколько разных соседей раньше, чем очередь дошла до её первой обработки) — алгоритм при этом всё равно завершится (ведь каждая вершина рано или поздно помечается и больше не добавляется), но будет выполнять лишнюю работу и хранить в очереди дублирующиеся записи. Для базового BFS с массивом visited правильная практика — помечать при постановке в очередь.

Разбор примеров

Пример 1 (лёгкий). Тот же граф-«путь» 1–2–3–4 из предыдущего раздела. Найти BFS-расстояния от вершины 1 до всех остальных.

from collections import deque

graph = {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}

def bfs_distances(graph, start):
    visited = {start}
    dist = {start: 0}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for u in graph[v]:
            if u not in visited:
                visited.add(u)
                dist[u] = dist[v] + 1
                queue.append(u)
    return dist

print(bfs_distances(graph, 1))  # {1: 0, 2: 1, 3: 2, 4: 3}

На линейном графе расстояния совпадают со «здравым смыслом»: чтобы дойти от 1 до 4, нужно пройти три ребра — $1\to2\to3\to4$ — и именно это число dist[4] = 3 алгоритм и вычисляет, обрабатывая вершины слоями: сначала слой $\{2\}$ на расстоянии 1, потом слой $\{3\}$ на расстоянии 2, потом слой $\{4\}$ на расстоянии 3.

Пример 2 (средний, граф с циклом и разными путями). Вершины 1–6, рёбра: $(1,2), (1,3), (2,4), (3,4), (4,5), (2,6)$. Есть два разных пути от 1 до 4 — через 2 (длина 2) и через 3 (тоже длина 2) — а также «обманчиво длинный» путь через 6, которого на самом деле нет, потому что 6 тупиковая. Найти кратчайшее расстояние от 1 до 5.

from collections import deque

graph = {
    1: [2, 3],
    2: [1, 4, 6],
    3: [1, 4],
    4: [2, 3, 5],
    5: [4],
    6: [2],
}

def bfs_distances(graph, start):
    visited = {start}
    dist = {start: 0}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for u in graph[v]:
            if u not in visited:
                visited.add(u)
                dist[u] = dist[v] + 1
                queue.append(u)
    return dist

d = bfs_distances(graph, 1)
print(d[5])  # 3
print(d)     # {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 2}

Здесь видно ключевое: до вершины 4 существует два разных пути одинаковой длины (через 2 и через 3), но благодаря метке посещённых BFS обработает вершину 4 ровно один раз — при первом же обнаружении, и это гарантированно случится на минимальном расстоянии (2 ребра), потому что оба конкурирующих пути имеют одну и ту же длину и попадают в очередь на одном и том же шаге. До вершины 6 путь есть, но он тупиковый и никак не помогает добраться до 5 — BFS не тратит на него лишнего внимания, просто отмечает dist[6] = 2 и двигается дальше.

Пример 3 (сложный, ML — степени разделения в социальном графе). Смоделировать упрощённый граф друзей и найти «степень разделения» (число рукопожатий) между двумя конкретными пользователями — ровно та задача, которую решает LinkedIn под подписью «связь третьей степени».

from collections import deque

social_graph = {
    "Аня": ["Боря", "Вера"],
    "Боря": ["Аня", "Гоша"],
    "Вера": ["Аня", "Гоша", "Даша"],
    "Гоша": ["Боря", "Вера", "Егор"],
    "Даша": ["Вера"],
    "Егор": ["Гоша"],
}

def degrees_of_separation(graph, start, target):
    if start == target:
        return 0
    visited = {start}
    queue = deque([start])
    dist = {start: 0}
    while queue:
        v = queue.popleft()
        for u in graph[v]:
            if u not in visited:
                visited.add(u)
                dist[u] = dist[v] + 1
                if u == target:
                    return dist[u]
                queue.append(u)
    return -1  # target недостижима

print(degrees_of_separation(social_graph, "Аня", "Егор"))  # 3

Ответ 3 означает: кратчайший путь между Аней и Егором состоит из трёх рёбер — например, Аня → Боря → Гоша → Егор или Аня → Вера → Гоша → Егор (оба варианта одинаковой длины), то есть три «рукопожатия». Заметь ранний выход if u == target: return dist[u] — как только BFS впервые обнаруживает целевую вершину, можно сразу вернуть результат, не дожидаясь обхода всего графа, потому что первое обнаружение в BFS гарантированно происходит на кратчайшем расстоянии. Точно этот же приём используют реальные системы анализа социальных графов: не нужно строить полное дерево кратчайших путей до всех пользователей сети, если интересует расстояние ровно до одного конкретного человека.

Почему это важно

Гарантия минимальности пути — то, ради чего вообще выбирают BFS вместо DFS в задачах о расстоянии. DFS способен обойти весь граф и рано или поздно найти целевую вершину, но длина найденного им пути ничем не ограничена — он может «случайно» сначала уйти в сторону на десять шагов, хотя прямой путь был длиной в два. BFS структурно не может так ошибиться, потому что он в принципе не переходит к следующему слою, пока не обработал полностью текущий. Это ровно то свойство, на которое опираются GPS-навигаторы для «по числу перекрёстков», рекомендательные системы для «ближайших по интересам» пользователей и любые другие приложения, где нужен не просто «какой-то путь», а именно кратчайший.

Применение DFS: компоненты связности и обнаружение циклов

Интуиция: DFS как инструмент разметки территории

Если запустить DFS не с одной стартовой вершины, а последовательно с каждой ещё не посещённой вершины графа, то каждый такой запуск «закрасит» одним и тем же цветом ровно ту область графа, до которой можно добраться, не выходя за пределы связанных между собой вершин. Это ровно определение компоненты связности: максимальное множество вершин, каждая из которых достижима из каждой другой по рёбрам графа. Граф социальной сети из десятков разрозненных «пузырей», не связанных друг с другом ни одной дружбой, — это граф с несколькими компонентами связности, и DFS находит их все за один линейный проход.

Вторая классическая задача, которую элегантно решает DFS, — обнаружение циклов. Идея интуитивно прозрачна: если во время обхода ты натыкаешься на ребро, ведущее в вершину, которая уже находится в текущей цепочке обхода (а не просто когда-то была посещена в прошлом обходе другой ветки), — значит, ты замкнул кольцо, то есть нашёл цикл.

Алгоритм

Компоненты связности через DFS. Дан граф $G = (V, E)$. Завести общее множество visited и счётчик компонент count = 0. Для каждой вершины $v \in V$: если $v$ ещё не в visited — увеличить count на 1 и запустить dfs(v), которая пометит visited для всех вершин, достижимых из $v$. После перебора всех вершин count равен числу компонент связности.

Обнаружение цикла в неориентированном графе через DFS. При обходе из вершины $v$ в соседа $u$ по ребру $(v, u)$: если $u$ уже посещена и не является непосредственным родителем $v$ в дереве обхода — найден цикл. (Проверка «не родитель» нужна потому, что в неориентированном графе ребро $(v, u)$ и ребро $(u, v)$ — одно и то же ребро, и возврат «назад, откуда пришли» не является циклом, а является нормальной частью представления неориентированного графа списком смежности.)

Разбор примеров

Пример 1 (лёгкий, компоненты связности). Граф из шести вершин: рёбра $(1,2), (2,3)$ и отдельно $(4,5)$, а вершина 6 вообще без рёбер. Найти число компонент связности.

graph = {1: [2], 2: [1, 3], 3: [2], 4: [5], 5: [4], 6: []}

def count_components(graph):
    visited = set()
    count = 0
    def dfs(v):
        visited.add(v)
        for u in graph[v]:
            if u not in visited:
                dfs(u)
    for v in graph:
        if v not in visited:
            count += 1
            dfs(v)
    return count

print(count_components(graph))  # 3

Три компоненты: $\{1, 2, 3\}$, $\{4, 5\}$ и изолированная $\{6\}$. Внешний цикл for v in graph перебирает каждую вершину-«кандидата» на роль новой компоненты, а условие if v not in visited отфильтровывает те вершины, которые уже были закрашены каким-то предыдущим запуском DFS, — именно поэтому вершина 3 не порождает отдельного вызова dfs, хотя тоже стоит в цикле: к моменту, когда цикл до неё доходит, она уже посещена как часть компоненты, стартовавшей от вершины 1.

Пример 2 (средний, обнаружение цикла). Граф с рёбрами $(1,2), (2,3), (3,1)$ (треугольник — цикл) и отдельно граф-путь $(4,5), (5,6)$ (без циклов). Определить для каждого, есть ли цикл.

def has_cycle(graph):
    visited = set()
    def dfs(v, parent):
        visited.add(v)
        for u in graph[v]:
            if u not in visited:
                if dfs(u, v):
                    return True
            elif u != parent:
                return True  # сосед уже посещён и это не родитель -> цикл
        return False
    for v in graph:
        if v not in visited:
            if dfs(v, None):
                return True
    return False

triangle = {1: [2, 3], 2: [1, 3], 3: [1, 2]}
path = {4: [5], 5: [4, 6], 6: [5]}

print(has_cycle(triangle))  # True
print(has_cycle(path))      # False

В треугольнике обход из 1 идёт в 2, из 2 — в 3 (ещё не посещена), а из 3 сосед 1 уже посещён — и это не родитель текущей вершины 3 (родитель 3 — это 2), значит, найден настоящий цикл. В графе-пути обход из 5 в 6, а единственный сосед 6 — это 5, которая как раз и есть родитель 6, поэтому условие u != parent не срабатывает, и цикл корректно не находится, хотя формально ребро $(5,6)$ и $(6,5)$ в списке смежности выглядит как «возврат в посещённую вершину».

Пример 3 (сложный, ML — кластеризация графа знаний по связности). В графе знаний часть сущностей относится к кластеру «веб-разработка», часть — к изолированному кластеру «астрономия», без единой связи между ними. Найти оба кластера через компоненты связности и заодно проверить кластер на наличие циклов (циклические зависимости определений — сигнал, что граф знаний плохо структурирован).

knowledge_graph = {
    "HTML": ["CSS"],
    "CSS": ["HTML", "JavaScript"],
    "JavaScript": ["CSS"],
    "Звезда": ["Галактика"],
    "Галактика": ["Звезда", "Вселенная"],
    "Вселенная": ["Галактика"],
}

def connected_components(graph):
    visited = set()
    components = []
    def dfs(v, comp):
        visited.add(v)
        comp.append(v)
        for u in graph[v]:
            if u not in visited:
                dfs(u, comp)
    for v in graph:
        if v not in visited:
            comp = []
            dfs(v, comp)
            components.append(comp)
    return components

for comp in connected_components(knowledge_graph):
    print(sorted(comp))
# ['CSS', 'HTML', 'JavaScript']
# ['Вселенная', 'Галактика', 'Звезда']

DFS честно разделил граф знаний на два непересекающихся кластера — «веб-разработка» и «астрономия», — потому что между ними физически нет ни одного ребра. На практике именно так системы автоматической кластеризации сущностей находят тематические группы в больших графах знаний ещё до того, как применять более тяжёлые методы вроде графовых нейросетей: компоненты связности — это самый дешёвый и грубый, но абсолютно надёжный первый срез структуры графа.

Почему это важно

Поиск компонент связности и обнаружение циклов — не две изолированные задачки для учебника, а базовые операции проверки «здоровья» графа перед тем, как запускать над ним более сложную аналитику. Прежде чем строить рекомендательную систему поверх графа пользователей, разумно узнать, не распался ли граф на несвязанные острова (иначе рекомендации внутри одного острова никогда не «достанут» до другого). Прежде чем выполнять топологическую сортировку графа зависимостей (урок 262), необходимо сначала убедиться, что в графе нет цикла, — потому что если A зависит от B, B от C, а C снова от A, никакого корректного «линейного порядка выполнения» просто не существует, и DFS — это ровно тот инструмент, который эту патологию обнаруживает за один линейный проход, прежде чем что-то пойдёт не так на более позднем и дорогом этапе.

Применение BFS: кратчайший путь и анализ социальных графов

Интуиция: расстояние без предположений о структуре графа

BFS универсален там, где нужно строгое, гарантированное кратчайшее расстояние в невзвешенном графе — и не важно, насколько сложна и запутана структура связей: слоистая природа BFS сама разберётся, какой путь короче, без ручного перебора вариантов. Это критично именно потому, что в реальных социальных графах структура связей хаотична: у одного человека 5 друзей, у другого 5000, где-то плотные группы взаимно знакомых людей, а где-то длинные цепочки редких связей. BFS не заботится об этой сложности — он просто послойно расширяется наружу и рано или поздно доберётся до любой достижимой вершины по кратчайшему пути.

Алгоритм

Восстановление кратчайшего пути (не только расстояния) через BFS. Модификация базового BFS: наряду с dist[v] хранить parent[v] — вершину, из которой $v$ была впервые обнаружена. После завершения BFS путь от $s$ до произвольной достижимой $t$ восстанавливается обратным проходом: начать с $t$, повторно переходить к parent[текущая вершина], пока не дойдёшь до $s$, и развернуть получившуюся последовательность.

Разбор примеров

Пример 1 (лёгкий). На графе друзей из предыдущего раздела не просто узнать расстояние от Ани до Егора, а восстановить сам путь.

from collections import deque

social_graph = {
    "Аня": ["Боря", "Вера"],
    "Боря": ["Аня", "Гоша"],
    "Вера": ["Аня", "Гоша", "Даша"],
    "Гоша": ["Боря", "Вера", "Егор"],
    "Даша": ["Вера"],
    "Егор": ["Гоша"],
}

def shortest_path(graph, start, target):
    visited = {start}
    parent = {start: None}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        if v == target:
            break
        for u in graph[v]:
            if u not in visited:
                visited.add(u)
                parent[u] = v
                queue.append(u)
    if target not in parent:
        return None
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = parent[node]
    return path[::-1]

print(shortest_path(social_graph, "Аня", "Егор"))
# ['Аня', 'Боря', 'Гоша', 'Егор']

Массив parent — это то, чего не было в примерах предыдущего раздела, но что нужно почти в любом реальном приложении: одного числа «расстояние 3» недостаточно, если конечная цель — показать пользователю саму цепочку общих знакомых, ведущую от него к нужному человеку.

Пример 2 (средний, карта города как невзвешенный граф). Упрощённая карта города: перекрёстки — вершины, улицы между соседними перекрёстками — рёбра без весов (считаем, что все кварталы одинаковой длины). Найти кратчайший маршрут по числу кварталов от точки A до точки F.

from collections import deque

city_map = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D", "E"],
    "D": ["B", "C", "F"],
    "E": ["C", "F"],
    "F": ["D", "E"],
}

def shortest_path(graph, start, target):
    visited = {start}
    parent = {start: None}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        if v == target:
            break
        for u in graph[v]:
            if u not in visited:
                visited.add(u)
                parent[u] = v
                queue.append(u)
    path, node = [], target
    while node is not None:
        path.append(node)
        node = parent[node]
    return path[::-1]

print(shortest_path(city_map, "A", "F"))  # ['A', 'C', 'E', 'F'] или ['A', 'B', 'D', 'F']

Оба варианта пути — через C-E и через B-D — имеют одинаковую длину в 3 квартала, и который из них конкретно вернёт код, зависит от порядка перечисления соседей в списке смежности; оба ответа одинаково корректны, потому что задача BFS — найти какой-нибудь путь минимальной длины, а не единственно возможный. В реальном GPS-навигаторе этот же принцип применяется к графу с весами (расстояние или время в минутах), и там на смену BFS приходит алгоритм Дейкстры, который ты изучишь позже в курсе; но для «числа перекрёстков» без учёта расстояний обычный BFS уже даёт точный ответ.

Пример 3 (сложный, ML — степени разделения как признак для рекомендательной системы). В упрощённом графе интересов пользователей вычислить для одного пользователя расстояние (в рёбрах графа «пользователь-интерес») до всех остальных пользователей, чтобы ранжировать потенциальных друзей по «близости» интересов — BFS здесь используется не для навигации, а как источник признака для более сложной модели.

from collections import deque

# граф двудольный: пользователь связан с интересом, интерес связан с пользователями, у которых он есть
interest_graph = {
    "Аня": ["Python", "Данные"],
    "Python": ["Аня", "Боря", "Вера"],
    "Данные": ["Аня", "Вера"],
    "Боря": ["Python", "Дизайн"],
    "Дизайн": ["Боря"],
    "Вера": ["Python", "Данные"],
}

def bfs_closeness(graph, start):
    visited = {start}
    dist = {start: 0}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for u in graph[v]:
            if u not in visited:
                visited.add(u)
                dist[u] = dist[v] + 1
                queue.append(u)
    # оставляем только других пользователей (нечётное расстояние -> нельзя быть пользователем в двудольном графе на чётном шаге от старта)
    return {node: d for node, d in dist.items() if node[0].isupper() and node not in ("Python", "Данные", "Дизайн")}

print(bfs_closeness(interest_graph, "Аня"))
# {'Аня': 0, 'Боря': 4, 'Вера': 2}

Расстояние Вера: 2 (через общий интерес «Python» или «Данные» — оба на расстоянии одного ребра, а Вера ещё через одно) короче, чем Боря: 4 (Ане нужно дойти до Бори через два «хопа» по интересам без прямого общего пункта на первом уровне) — и эта разница в BFS-расстоянии по графу интересов вполне может использоваться как один из признаков в модели «предложить в друзья», наравне с числом общих знакомых. Важная оговорка: в реальных системах BFS-расстояние на графе с сотнями миллионов вершин обычно не считают «на лету» для каждого запроса, а предвычисляют приближёнными методами (например, HyperLogLog-оценками достижимости) — но сама идея «расстояние по графу как признак» берёт начало ровно в этом простом алгоритме.

Почему это важно

BFS даёт то, что не даёт почти ни один другой простой алгоритм: математически гарантированную минимальность найденного расстояния, вычисленную за линейное время без каких-либо предположений о структуре графа. Это ровно то свойство, которое превращает абстрактную операцию «обойти граф» в конкретную бизнес-метрику — «3-я степень связи» в LinkedIn, «за сколько поворотов доехать» в навигаторе, «насколько близки интересы» в рекомендательной системе. Там, где нужна не любая, а именно кратчайшая связь между двумя точками графа без весов на рёбрах, BFS — почти всегда правильный выбор по умолчанию.

Сложность DFS и BFS: почему оба работают за O(V + E)

Оба алгоритма посещают каждую вершину ровно один раз (благодаря метке visited) — это даёт слагаемое $O(V)$. А для каждой посещённой вершины алгоритм один раз проходит по всему её списку соседей, чтобы решить, кого добавить в стек или очередь дальше, — суммарно по всем вершинам это ровно $O(E)$ операций для неориентированного графа (каждое ребро просматривается дважды, по разу с каждого конца, что не меняет асимптотику) или $O(E)$ для ориентированного (каждое ребро просматривается один раз, со стороны вершины-источника). В сумме получается $O(V + E)$ — линейная сложность относительно суммарного размера графа, куда бы ты ни экономил: ни одна вершина, ни одно ребро не обрабатываются повторно благодаря метке посещённых.

Эта оценка справедлива именно при хранении графа в виде списка смежности. Если бы граф хранился в виде матрицы смежности, для каждой вершины пришлось бы проверять всю строку матрицы в поисках соседей — это $O(V)$ на вершину и $O(V^2)$ суммарно, что заметно хуже для разреженных графов (мало рёбер относительно вершин, как в большинстве реальных социальных графов). Ровно поэтому в уроке 260 список смежности был назван предпочтительным представлением для алгоритмов обхода: DFS и BFS «дружат» именно с ним, реализуя свою теоретическую линейную сложность на практике, а не только на бумаге.

Практика: 30 заданий

Базовые (задания 1–10)

Задание 1: Дан граф {1: [2, 3], 2: [1], 3: [1]}. Выполни DFS от вершины 1 вручную (на бумаге) и запиши порядок посещения вершин.

Задание 2: На том же графе {1: [2, 3], 2: [1], 3: [1]} выполни BFS от вершины 1 и укажи dist для каждой вершины.

Задание 3: Объясни своими словами, почему обход дерева (урок 253/256) может обойтись без множества visited, а обход произвольного графа — нет.

Задание 4: Дан граф с циклом {1: [2], 2: [1, 3], 3: [2, 1]} (треугольник). Что произойдёт при запуске DFS от вершины 1 БЕЗ проверки if u not in visited перед рекурсивным вызовом? Опиши первые 6 шагов.

Задание 5: Дан граф {"A": ["B"], "B": ["A", "C"], "C": ["B"], "D": ["E"], "E": ["D"]}. Сколько в нём компонент связности?

Задание 6: В чём разница между структурой данных, которую использует DFS (итеративная версия), и структурой, которую использует BFS?

Задание 7: Дан граф друзей {"Ира": ["Ким"], "Ким": ["Ира", "Лев"], "Лев": ["Ким"]}. Через сколько «рукопожатий» Ира знакома со Львом?

Задание 8: Почему в BFS правильно помечать вершину как посещённую в момент добавления в очередь, а не в момент извлечения из неё?

Задание 9: Дан ориентированный граф {"A": ["B"], "B": ["C"], "C": []}. Есть ли в нём цикл? Обоснуй, используя идею DFS.

Задание 10: Сформулируй одним предложением, чем задача, которую решает DFS (компоненты связности), принципиально отличается от задачи, которую решает BFS (кратчайший путь).

Средние (задания 11–20)

Задание 11: Реализуй функцию is_connected(graph), которая возвращает True, если граф связен целиком (одна компонента связности), и False иначе.

Задание 12: Дан граф {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3]} (квадрат с диагоналями через общих соседей 2 и 3). Есть ли в нём цикл? Если да — укажи один из циклов явно.

Задание 13: Напиши функцию bfs_path_exists(graph, start, target), которая возвращает True, если между start и target вообще существует путь (не важно, какой длины), и False иначе.

Задание 14: В графе {"Пост1": ["Пост2", "Пост3"], "Пост2": ["Пост1"], "Пост3": ["Пост1", "Пост4"], "Пост4": ["Пост3"], "Пост5": []} (граф репостов в соцсети) найди все компоненты связности.

Задание 15: Почему для проверки цикла в неориентированном графе нужно явно исключать «родителя» текущей вершины из проверки, а для ориентированного графа — нет?

Задание 16: Дан взвешенный по количеству кварталов (но без явных весов в рёбрах — граф просто содержит соседние перекрёстки) граф улиц. Обоснуй, почему для поиска «кратчайшего пути по числу перекрёстков» БЕЗ учёта фактических расстояний в метрах BFS даёт точный ответ, а не приближённый.

Задание 17: Напиши функцию bfs_shortest_path_length(graph, start, target), возвращающую длину кратчайшего пути (число рёбер) или -1, если пути не существует.

Задание 18: В графе знаний {"ML": ["Статистика", "Программирование"], "Статистика": ["ML", "Матанализ"], "Программирование": ["ML"], "Матанализ": ["Статистика"], "История": ["Философия"], "Философия": ["История"]} найди, сколько тематических кластеров образует этот граф, и назови их.

Задание 19: Объясни, почему рекурсивная реализация DFS на очень большом графе (например, цепочка из 50 000 последовательно связанных вершин) может упасть с ошибкой переполнения стека, а BFS с такой же по размеру очередью — нет.

Задание 20: В графе пользователей {"P1": ["P2", "P3"], "P2": ["P1", "P4"], "P3": ["P1", "P4"], "P4": ["P2", "P3", "P5"], "P5": ["P4"]} найди BFS-расстояния от P1 до всех остальных пользователей и определи, у кого из них расстояние наибольшее.

Сложные (задания 21–30)

Задание 21: Докажи (неформально, в 3–4 предложения) корректность утверждения: «в BFS, если вершина $u$ впервые обнаружена во время обработки вершины $v$, то $\text{dist}[u] = \text{dist}[v] + 1$, и это минимальное возможное расстояние до $u$».

Задание 22: Реализуй функцию find_all_components_with_cycles(graph), которая для неориентированного графа возвращает список компонент связности, помеченных флагом — содержит ли эта конкретная компонента хотя бы один цикл.

Задание 23: В ориентированном графе {"A": ["B"], "B": ["C"], "C": ["A"]} наивная проверка цикла из задания 15 (сравнение с родителем) даёт неверный ответ, если применить её как есть (для неориентированного графа). Модифицируй алгоритм для корректного обнаружения цикла в ОРИЕНТИРОВАННОМ графе.

Задание 24: В социальном графе с 1000 пользователями и в среднем 50 друзьями у каждого оцени порядок величины числа операций, которое выполнит BFS для поиска расстояния от одного конкретного пользователя до другого.

Задание 25: Почему для реального графа Facebook или LinkedIn (миллиарды вершин) наивный BFS «на лету» для каждого запроса «степени разделения» становится проблематичным, даже несмотря на линейную сложность $O(V+E)$?

Задание 26: Реализуй BFS, который одновременно строит слои графа (список вершин на каждом расстоянии от старта) — это полезно, например, чтобы показать «друзей 1-го, 2-го, 3-го уровня» отдельными списками.

Задание 27: Дан двудольный граф «пользователь — группа»: пользователь связан с каждой группой, в которой состоит. Объясни, почему BFS-расстояние между двумя ПОЛЬЗОВАТЕЛЯМИ в таком графе всегда чётное число.

Задание 28: Модифицируй DFS для поиска компонент связности так, чтобы функция сразу возвращала размер (число вершин) самой большой компоненты — это полезно, например, чтобы оценить размер «основного ядра» социальной сети относительно случайных изолированных пар пользователей.

Задание 29: Объясни, почему для поиска кратчайшего пути во ВЗВЕШЕННОМ графе (у рёбер разные «стоимости», например время в минутах, а не просто число перекрёстков) обычный BFS уже не даёт корректного ответа, даже если веса всех рёбер положительны.

Задание 30 (обобщающее): Сформулируй, в каком порядке ты бы применил DFS и BFS, если бы тебе дали новый, совершенно неизвестный граф социальной сети и попросили: (а) проверить, что граф не распадается на изолированные острова, (б) убедиться, что в нём нет циклов «взаимных рекомендаций» определённого вида, и (в) найти степень разделения между двумя конкретными пользователями. Обоснуй порядок.

Частые ошибки

Ошибка 1. Забывают заводить и проверять множество посещённых вершин при переносе алгоритма обхода с дерева на произвольный граф.

Как выглядит: код, написанный по образцу обхода дерева из урока 253/256, без единой строчки про visited, запускается на графе с циклом и «зависает» — программа не завершается или падает с ошибкой переполнения стека вызовов.

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

Как правильно: при любом обходе произвольного графа (не дерева!) первым делом, ещё до написания логики самого обхода, завести множество visited и проверять принадлежность к нему перед каждым переходом в соседнюю вершину (см. задание 4, где явно разобрано, что происходит без этой проверки).

Ошибка 2. В BFS помечают вершину посещённой в момент извлечения из очереди, а не в момент добавления в неё.

Как выглядит: одна и та же вершина добавляется в очередь несколько раз (от разных соседей на одном слое), что приводит к лишним, дублирующимся операциям обработки и потенциально неверным значениям dist при неаккуратной реализации.

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

Как правильно: помечать вершину как visited сразу в момент добавления в очередь — это гарантирует, что каждая вершина попадёт в очередь ровно один раз (см. разбор алгоритма BFS и задание 8).

Ошибка 3. Путают DFS и BFS в задачах, где нужен именно кратчайший путь, и применяют DFS, ожидая минимальной длины пути.

Как выглядит: код корректно находит какой-то путь от старта до цели через DFS, но длина этого пути не минимальна, потому что DFS мог случайно сначала «нырнуть» в длинную ветвь.

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

Как правильно: для задач о минимальном числе рёбер использовать исключительно BFS — только его послойная структура математически гарантирует, что первое обнаружение цели происходит на кратчайшем расстоянии (см. пример 2 и пример 3 в разделе про BFS).

Ошибка 4. При обнаружении цикла в неориентированном графе через DFS забывают исключить из проверки родителя текущей вершины и получают ложные срабатывания на любом графе без единого настоящего цикла.

Как выглядит: даже на графе-пути (простая цепочка вершин без циклов) алгоритм сообщает о найденном цикле.

Почему возникает: в списке смежности неориентированного графа ребро $(v, u)$ хранится в обе стороны, и наивная проверка «сосед уже посещён» автоматически, ошибочно, срабатывает на возврат в родителя — то есть на само ребро, по которому только что пришли, а не на настоящий цикл.

Как правильно: всегда передавать в рекурсию информацию о родителе текущей вершины и явно исключать его из проверки «сосед уже посещён» (см. задание 15 и алгоритм обнаружения цикла в разделе про применения DFS).

Ошибка 5. Используют матрицу смежности для DFS/BFS на большом разреженном графе, не замечая, что это превращает теоретическую линейную сложность $O(V+E)$ в реальную квадратичную $O(V^2)$.

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

Почему возникает: формула $O(V+E)$ в учебнике молчаливо подразумевает хранение графа списком смежности; для матрицы смежности поиск соседей вершины требует просмотра целой строки длины $V$, а не только реальных соседей.

Как правильно: для алгоритмов обхода почти всегда выбирать список смежности (урок 260) — особенно для разреженных графов, где $E \ll V^2$, что типично для большинства реальных социальных графов, графов знаний и карт дорог.

Главное запомнить

DFS (обход в глубину) идёт максимально далеко в одном направлении, прежде чем вернуться назад и попробовать другое; использует стек (явный или через рекурсию).
BFS (обход в ширину) расширяется слоями, обрабатывая сначала все вершины на расстоянии 1 ребро от старта, потом 2, потом 3 и так далее; использует очередь (структуру FIFO).
Метка посещённых вершин (visited) обязательна на графах с циклами — без неё оба алгоритма могут зациклиться и никогда не завершиться, в отличие от обхода дерева, где эта проблема структурно невозможна.
В BFS правильно помечать вершину посещённой в момент добавления в очередь, а не в момент извлечения — это предотвращает повторные добавления одной и той же вершины.
DFS решает задачи о структуре и достижимости: поиск компонент связности (все вершины, достижимые друг из друга) и обнаружение циклов (в неориентированном графе — через проверку «сосед уже посещён и не родитель»).
BFS решает задачи о точном минимальном расстоянии в невзвешенном графе — числе рёбер на кратчайшем пути; это ключевое приложение — вычисление «степеней разделения» в социальных графах.
Оба алгоритма работают за $O(V+E)$ при хранении графа списком смежности — каждая вершина посещается один раз, каждое ребро просматривается константное число раз.
BFS не подходит для взвешенных графов — он минимизирует только число рёбер, игнорируя их веса; для взвешенных кратчайших путей нужен другой алгоритм (например, Дейкстра).
DFS удобно реализовать рекурсивно для читаемости, но на очень глубоких графах предпочтительнее итеративная версия с явным стеком, чтобы избежать переполнения стека вызовов.
Проверка на цикл через DFS в неориентированном графе требует сравнения с родителем; в ориентированном графе для этого нужна схема с тремя состояниями вершин (белый/серый/чёрный).

Связь с другими темами курса

Что нужно было знать до этого урока

Этот урок напрямую опирается на представление графов списком смежности и матрицей смежности (урок 260) — без понимания того, как граф хранится в памяти, невозможно написать код обхода. Он также использует стек и очередь как структуры данных из урока 253, только что применённые не к абстрактным элементам, а к вершинам графа, и обобщает обход в глубину и обход в ширину дерева (уроки 253 и 256) на случай произвольного графа, где, в отличие от дерева, могут быть циклы. Базовые понятия графа — вершина, ребро, степень, связность, цикл — из урока 259 используются здесь без повторного объяснения.

Что изучить дальше

В следующем уроке, 262 «Топологическая сортировка», ты увидишь прямое развитие идей DFS на ориентированных ациклических графах (DAG): как выстроить вершины графа зависимостей в линейный порядок так, чтобы каждая вершина шла раньше всех вершин, зависящих от неё. Один из классических алгоритмов топологической сортировки строится ровно на DFS, разобранном в этом уроке, с добавлением одной детали — порядка завершения обработки вершин. Позже в блоке про алгоритмы на графах тебе встретятся алгоритм Дейкстры (BFS для взвешенного графа) и алгоритм Флойда — Уоршелла для кратчайших путей между всеми парами вершин сразу — оба опираются на интуицию «расширения от старта», впервые встреченную здесь в BFS.

Где это нужно в жизни

🤖 ML/AI. BFS вычисляет степени разделения в социальных графах — признак, который используется в рекомендательных системах и в задачах предсказания связей между вершинами; DFS находит компоненты связности и кластеры в графах знаний, а обнаружение циклов через DFS предотвращает некорректные зависимости в пайплайнах обработки данных и в вычислительных графах нейросетей (граф вычислений в PyTorch/TensorFlow обязан быть ациклическим).

🗺️ Навигация и логистика. BFS в невзвешенном графе перекрёстков даёт маршрут с минимальным числом поворотов; в графах с весами (расстояние, время) та же идея расширяется до алгоритма Дейкстры, который используют реальные GPS-навигаторы.

🌐 Веб и поисковые системы. Поисковые роботы обходят граф интернета (страницы — вершины, ссылки — рёбра) с помощью вариаций DFS и BFS, а обнаружение циклов в графе ссылок помогает избежать бесконечного зацикливания робота на кольце взаимных ссылок.

📊 Анализ данных и инфраструктура. DFS проверяет ациклические зависимости в системах сборки (Make, CI/CD пайплайны) и в системах управления пакетами — цикл зависимостей означает, что установить пакеты в правильном порядке невозможно, и это ровно та проверка, которую делает алгоритм обнаружения цикла из этого урока.

Интересные факты

Механическая мышь «Тесей», построенная Клодом Шенноном в 1950 году, — один из первых в истории примеров работающего искусственного интеллекта: она находила выход из лабиринта, эффективно выполняя алгоритм, эквивалентный обходу графа, и «запоминала» пройденный маршрут магнитными реле под полем лабиринта — ранний физический аналог массива visited.
Идея пометки пройденного пути для навигации в лабиринте — нить Ариадны из греческого мифа о Тесее и Минотавре — часто приводится как метафора DFS: герой заходит в лабиринт (граф), разматывая нить (стек вызовов), и по этой же нити возвращается назад, когда упирается в тупик.
Алгоритм Дейкстры для кратчайших путей во взвешенном графе, который ты изучишь позже в курсе, при равных весах всех рёбер математически в точности вырождается в BFS — это не совпадение, а прямое следствие того, что оба алгоритма решают одну и ту же задачу «минимизировать сумму весов на пути», просто BFS — частный случай с весом 1 у каждого ребра.
В теории малых миров знаменитый эксперимент психолога Стэнли Милгрэма 1960-х годов о «шести рукопожатиях» между любыми двумя людьми на Земле — по сути, эмпирическая гипотеза о том, что BFS-расстояние в графе всех человеческих знакомств на планете в среднем на удивление мало, порядка 6, несмотря на миллиарды вершин в этом графе.

Лайфхаки

Перед тем как писать код обхода, задай себе один вопрос: «может ли в этом графе быть цикл?». Если да или если не уверен — сразу заводи visited в первой же строке функции, не дожидаясь, пока программа зависнет на тестовом запуске.
Выбирай DFS или BFS исходя из формы вопроса, а не по привычке. Вопрос «связаны ли вообще» или «сколько изолированных групп» — DFS. Вопрос «сколько шагов (рёбер) минимум» — BFS. Смешивать их в задачах о минимальном расстоянии — гарантированная ошибка.
В Python используй collections.deque для очереди BFS, а не обычный список с pop(0). Удаление с начала обычного списка — операция за $O(n)$, а deque.popleft() — за $O(1)$; на больших графах разница превращается в заметное замедление.
Если граф может быть очень глубоким (длинные цепочки), предпочитай итеративный DFS с явным стеком рекурсивному — это избавляет от риска упереться в системный лимит глубины рекурсии на неожиданно большом входном графе.
Держи в голове шпаргалку по сложности при хранении графа: список смежности + DFS/BFS = $O(V+E)$, матрица смежности + DFS/BFS = $O(V^2)$ из-за поиска соседей построчным сканированием. Для разреженных графов (типичный случай в реальных данных) разница может быть на порядки.
Для восстановления самого пути, а не только его длины, всегда добавляй массив parent параллельно с dist в BFS — это стоит одной дополнительной строки кода, но избавляет от необходимости переписывать алгоритм позже, когда потребуется не только «сколько», но и «как именно».
Проверяй свою реализацию обхода на графе с намеренно вставленным циклом, а не только на графе-дереве. Тестирование только на ациклических графах — самая частая причина того, что баг с забытой меткой visited не проявляется на этапе разработки и всплывает только на реальных данных.

Обход графов — это тот редкий момент в курсе алгоритмов, где две простые, буквально в десяток строк кода идеи закрывают огромный пласт практических задач: от «покажи мне общих знакомых» до «есть ли ошибка в зависимостях моего проекта». DFS и BFS не заменяют друг друга — они отвечают на принципиально разные вопросы о графе, и умение сразу увидеть, какой из двух вопросов перед тобой стоит, — это тот навык, который дальше будет постоянно всплывать во всех следующих алгоритмах на графах, от топологической сортировки в следующем уроке до полноценных алгоритмов кратчайших путей на взвешенных графах.

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку

💬 Нашёл ошибку или есть вопрос по уроку? Написать в Telegram →