Обходы графа, связность и деревья

Учимся систематически обходить граф, находить компоненты связности и понимать деревья — основу множества структур данных.

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

Зачем нужны обходы и деревья

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

Два способа обойти граф

Есть два фундаментальных порядка обхода, и их стоит твёрдо различать.

Обход в ширину (BFS, breadth-first search) — идём «волнами»: сначала все соседи старта, потом соседи соседей, и так далее. Используется очередь. BFS находит кратчайший путь (по числу рёбер) в невзвешенном графе.
Обход в глубину (DFS, depth-first search) — идём «вглубь» по одному пути до упора, потом возвращаемся и пробуем другие ветки. Используется стек (или рекурсия). DFS удобен для поиска циклов, компонент связности, топологической сортировки.

Разница в одной структуре данных: BFS берёт из очереди (первым пришёл — первым ушёл), DFS — из стека (последним пришёл — первым ушёл). Эта мелочь полностью меняет порядок обхода.

BFS и DFS на Python

from collections import deque

# Граф-«цикл с диагоналями» из 6 вершин
g = {1: [2, 3], 2: [1, 4], 3: [1, 4, 5],
     4: [2, 3, 6], 5: [3, 6], 6: [4, 5]}

def bfs(g, start):
    seen = {start}
    order = []
    queue = deque([start])
    while queue:
        v = queue.popleft()      # берём из НАЧАЛА очереди
        order.append(v)
        for u in g[v]:
            if u not in seen:
                seen.add(u)
                queue.append(u)
    return order

def dfs(g, start, seen=None, order=None):
    if seen is None:
        seen, order = set(), []
    seen.add(start)
    order.append(start)
    for u in g[start]:
        if u not in seen:
            dfs(g, u, seen, order)
    return order

print("BFS из вершины 1:", bfs(g, 1))
print("DFS из вершины 1:", dfs(g, 1))

Вывод:

BFS из вершины 1: [1, 2, 3, 4, 5, 6]
DFS из вершины 1: [1, 2, 4, 3, 5, 6]

Видишь разницу в порядке? BFS сначала навестил обоих соседей единицы (2 и 3), потом пошёл дальше «вширь». DFS же из 1 ушёл в 2, оттуда сразу вглубь в 4, и только исчерпав эту ветку, вернулся к 3. Один и тот же граф — два разных маршрута, и каждый хорош для своих задач.

Компоненты связности

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

# Граф из трёх «островов»: {1,2}, {3,4}, {5}
g2 = {1: [2], 2: [1], 3: [4], 4: [3], 5: []}

def components(g):
    seen = set()
    result = []
    for v in g:
        if v not in seen:
            comp = []
            stack = [v]
            while stack:
                x = stack.pop()
                if x in seen:
                    continue
                seen.add(x)
                comp.append(x)
                stack.extend(g[x])
            result.append(sorted(comp))
    return result

print("Компоненты связности:", components(g2))

Вывод:

Компоненты связности: [[1, 2], [3, 4], [5]]

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

Деревья и их магическое свойство

Дерево — связный граф без циклов. У деревьев есть удивительно жёсткое свойство, которое стоит запомнить:

В дереве с n вершинами ровно n − 1 рёбер.

Интуиция: чтобы связать n вершин, нужно минимум n−1 ребро (каждое новое ребро присоединяет одну новую вершину). Меньше — граф развалится на куски; больше — появится цикл. Дерево балансирует на грани: оно связно (как раз хватает рёбер) и при этом без циклов (ни одного лишнего). Отсюда эквивалентные определения дерева: связный граф с n−1 рёбрами; граф, где между любыми двумя вершинами ровно один путь. Проверим свойство кодом.

# Дерево из 5 вершин
tree = {1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}

n = len(tree)
m = sum(len(adj) for adj in tree.values()) // 2   # рёбра (делим на 2)
print(f"Вершин n = {n}, рёбер m = {m}")
print(f"n - 1 = {n - 1}")
print("Это дерево (m == n-1 и связно):", m == n - 1)

Вывод:

Вершин n = 5, рёбер m = 4
n - 1 = 4
Это дерево (m == n-1 и связно): True

Пять вершин, четыре ребра — ровно n−1. Это свойство — рабочий инструмент: добавили ребро в дерево — гарантированно получили цикл; убрали ребро — гарантированно разорвали на две части. Поэтому дерево называют «минимально связным» графом.

Социальные сети как графы: шесть рукопожатий

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

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

Типичные ошибки

Не помечать посещённые вершины. Без множества seen обход зациклится на графах с циклами — будет ходить по кругу вечно.
Путать BFS и DFS по структуре данных. BFS — очередь (popleft), DFS — стек (pop) или рекурсия. Перепутаешь — получишь не тот порядок.
Считать любой связный граф деревом. Дерево — связный и без циклов. Связный граф с циклом — не дерево, и рёбер в нём больше n−1.

Итог

BFS обходит «вширь» через очередь (находит кратчайший путь), DFS — «вглубь» через стек/рекурсию.
Компоненты связности находят запуском обхода от каждой непосещённой вершины.
Дерево — связный граф без циклов; в нём ровно n − 1 рёбер.
Дерево «минимально связно»: убери ребро — распадётся, добавь — появится цикл.