Граф и обходы BFS и DFS: как пройти лабиринт двумя способами

Граф — это точки, соединённые линиями, и почти любую задачу про «связи» и «пути» можно свести к обходу графа.

Обойти граф можно двумя способами: расходясь от старта ровными кругами (в ширину) или забегая как можно дальше по одной тропе (в глубину).

Что такое граф

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

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

Как граф хранят в коде

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

Главный вопрос: как всё обойти

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

Поиск в ширину (BFS): расходимся кругами

Поиск в ширину исследует граф слоями. Сначала — стартовая вершина. Потом все её прямые соседи (один шаг от старта). Потом соседи соседей (два шага). И так, расходясь ровными кругами, как волны от брошенного в воду камня.

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

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()     # берём из головы очереди
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

graph = {
    "A": ["B", "C"], "B": ["A", "D"],
    "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"],
}
print(bfs(graph, "A"))   # A, потом B C, потом D, потом E

Поиск в глубину (DFS): ныряем до упора

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

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

def dfs(graph, start, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(start)
    order.append(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, order)   # ныряем глубже
    return order

print(dfs(graph, "A"))   # A, B, D, C, E — сначала вглубь

Один граф, два характера

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