Алгоритмы на графах для собеседований: BFS/DFS, топологическая сортировка и кратчайшие пути

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

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

Как думать о графе на интервью: представление и оценки

Прежде чем бежать писать код, полезно зафиксировать три вещи:

1. Что является вершинами: индексы узлов, состояния в автомате, курсы в программе, комнаты в лабиринте и т. п.
2. Что является рёбрами и направленность: ориентированный граф (зависимости) или неориентированный (двусторонние связи).
3. Какой смысл у рёбер:
   • просто «можно перейти» (без веса),
   • «есть стоимость» (вес, расстояние, цена),
   • «нужно найти кратчайшее число шагов» (тоже вес, но обычно единичный).

Списки смежности vs матрица

На интервью обычно ожидают два стандартных представления:

• Список смежности: adj[v] — список соседей.
  Подходит для большинства задач, особенно когда граф разреженный.
• Матрица смежности: matrix[u][v] — есть ребро или нет.
  Удобна, если нужны быстрые проверки наличия ребра O(1), но по памяти обычно хуже: O(V^2).

Быстрая оценка сложности

Обозначим:

• V — число вершин,
• E — число рёбер.

Типовые факты:

• Проход по графу списками смежности (BFS/DFS): O(V + E).
• Топологическая сортировка (Кан или DFS-подход): тоже O(V + E).
• Кратчайшие пути:
  • BFS в не-взвешенном графе (все рёбра “равны по стоимости”): O(V + E)
  • Дейкстра (веса неотрицательные) с приоритетной очередью: O((V + E) log V)
  • Беллман–Форд (произвольные веса, включая отрицательные): O(V·E)
  • Флойд–Уоршелл (все пары): O(V^3)

На собеседовании обычно достаточно правильно выбрать алгоритм под условия, чтобы решение выглядело «естественным».

BFS и DFS: когда именно они нужны

DFS (обход в глубину): компоненты, циклы, связность

DFS рекурсивно или итеративно идёт “вглубь”, пока возможно, затем возвращается.

Типичные задачи:

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

DFS на неориентированном графе: связность

Идея: если можно добраться из s до v, значит вершины в одной компоненте.

def dfs_component(start, adj):
    n = len(adj)
    stack = [start]
    visited = [False] * n
    visited[start] = True

    while stack:
        v = stack.pop()
        for to in adj[v]:
            if not visited[to]:
                visited[to] = True
                stack.append(to)

    return visited

Сложность: O(V + E) в худшем случае, так как каждая вершина и ребро обрабатываются ограниченное число раз.

Циклы в ориентированном графе: “цвета” вершин

Одна из самых частых ловушек: в ориентированном графе простой visited недостаточен — нужно различать вершины текущего стека рекурсии и уже полностью обработанные.

Классическая схема:

• 0 — не посещена,
• 1 — в процессе (в стеке),
• 2 — обработана полностью.

Если во время обхода наткнулись на вершину со статусом 1, это цикл.

def has_cycle_directed(adj):
    n = len(adj)
    state = [0] * n  # 0=white, 1=gray, 2=black

    def dfs(v):
        state[v] = 1
        for to in adj[v]:
            if state[to] == 1:
                return True  # back edge => cycle
            if state[to] == 0 and dfs(to):
                return True
        state[v] = 2
        return False

    for v in range(n):
        if state[v] == 0 and dfs(v):
            return True
    return False

Сложность: O(V + E).

Граничные случаи:

• самопетля v -> v сразу даёт цикл;
• граф может быть несвязным — нужно запускать DFS от всех непосещённых вершин.

BFS: кратчайший путь в не-взвешенном графе, уровни и расстояния

BFS идёт по “слоям” — сначала все вершины на расстоянии 1 от старта, затем на расстоянии 2 и т. д. Это делает BFS идеальным для задач вида:

• «минимальное число шагов от s до t»
• «найти расстояния до всех вершин»
• «найти первый раз, когда достигли условие» (например, клетку с ключом)

BFS с расстояниями

from collections import deque

def bfs_distances(adj, start):
    n = len(adj)
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])

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

    return dist

Сложность: O(V + E).

Почему решение корректно:

• BFS гарантирует, что вершины извлекаются из очереди в порядке возрастания расстояния;
• первое присваивание dist[to] даёт кратчайшее число рёбер.

Частая ошибка: BFS без “раннего” посещения

Если вы добавляете вершину в очередь много раз, усложняете анализ и иногда ломаете корректность. Важно:

• помечать visited/dist в момент добавления в очередь, а не при извлечении.

Понимание формулировок: как из текста сделать граф

На интервью задачи редко приходят в виде “дан граф, найдите BFS”. Чаще — это текстовая формулировка. Разберём типовые шаблоны.

1) “Зависимости” → ориентированный граф + поиск достижимости/цикл/топосортировка

Примеры:

• курсы и предварительные требования,
• задания, которые можно начать только после других,
• “можно ли выполнить все задачи” (вопрос о циклах).

Если есть зависимость A -> B (сначала A, потом B), то это ребро из A в B.

Тогда:

• наличие цикла означает невозможность выполнить все задачи;
• топологическая сортировка даёт порядок выполнения.

2) “Переходы” → граф состояний + BFS/DFS

Примеры:

• лабиринт,
• переходы между комнатами,
• минимальное число операций (например, удвоить/прибавить/уменьшить в пределах диапазона).

Тогда вершины — состояния, рёбра — допустимые переходы.
Если стоимость каждого шага одинакова — BFS, если нужно исследовать все варианты — DFS/комбинированные подходы.

3) “Стоимость пути” → взвешенный граф и выбор кратчайшего пути

• Если веса неотрицательные — Дейкстра.
• Если веса могут быть отрицательными — Беллман–Форд (или другие специализированные).
• Если веса везде одинаковые (например, каждая дуга стоит 1) — BFS.

Топологическая сортировка: порядок зависимостей без циклов

Топологическая сортировка применима только к DAG (направленный ациклический граф). Смысл: вернуть порядок вершин так, чтобы для любого ребра u -> v вершина u стояла раньше v.

На интервью встречаются два варианта вопроса:

1. «Дайте любой допустимый порядок выполнения» (если он существует).
2. «Выведите, можно ли выполнить все задания / есть ли цикл» (тут топосортировка часто выступает как проверка).

Подход 1: алгоритм Кана (подавление in-degree)

Идея:

• считаем in_degree[v] — сколько рёбер входит в вершину;
• кладём в очередь все вершины с in_degree = 0;
• вынимаем, добавляем в ответ и уменьшаем in_degree у соседей.

Если в конце мы не обработали все вершины — значит есть цикл.

from collections import deque

def topological_sort_kahn(adj):
    n = len(adj)
    indeg = [0] * n
    for v in range(n):
        for to in adj[v]:
            indeg[to] += 1

    q = deque([v for v in range(n) if indeg[v] == 0])
    order = []

    while q:
        v = q.popleft()
        order.append(v)
        for to in adj[v]:
            indeg[to] -= 1
            if indeg[to] == 0:
                q.append(to)

    if len(order) != n:
        return None  # cycle exists
    return order

Сложность: O(V + E).

Нюансы:

• Вопрос “любой ли порядок” — да, алгоритм вернёт один из возможных.
• Если просят лексикографически минимальный порядок, надо использовать структуру данных со свойством минимума (например, heap). Но это уже отдельная вариация.

Подход 2: DFS + стек (postorder)

Можно сделать через DFS: вершину помещают в результат после обработки всех её исходящих рёбер. Затем порядок обычно разворачивают.

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

Кратчайшие пути: выбор алгоритма по типу весов

Не-взвешенный граф (или все веса равны 1): BFS

Если ребро соответствует “одному шагу”, то BFS даёт кратчайший путь по числу рёбер.

Признак в формулировке:

• “минимальное число переходов”
• “минимальная длина в рёбрах”
• “каждый ход одинаково стоит”

Взвешенный граф с неотрицательными весами: Дейкстра

Если веса w(u, v) >= 0, и нужно минимизировать сумму весов, то Дейкстра — базовый стандарт.

Пример реализации (adj list)

import heapq

def dijkstra(adj, start):
    n = len(adj)
    INF = 10**18
    dist = [INF] * n
    dist[start] = 0
    pq = [(0, start)]  # (distance, vertex)

    while pq:
        d, v = heapq.heappop(pq)
        if d != dist[v]:
            continue  # устаревшая запись в очереди
        for to, w in adj[v]:
            nd = d + w
            if nd < dist[to]:
                dist[to] = nd
                heapq.heappush(pq, (nd, to))

    return dist

Сложность: O((V + E) log V).

Подводные камни:

• В очереди могут лежать устаревшие пары (d, v). Фильтрация if d != dist[v] обязательна.
• Если граф очень плотный, можно обсуждать матричные оптимизации, но на собеседовании обычно достаточно списка смежности.

Отрицательные веса: Беллман–Форд

Если веса могут быть отрицательными, но нет отрицательных циклов (или нужно проверить их наличие), Беллман–Форд становится способом «в лоб» за O(V·E).

Ключевые особенности:

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

def bellman_ford(edges, n, start):
    INF = 10**18
    dist = [INF] * n
    dist[start] = 0

    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break

    # проверка на отрицательный цикл
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None  # отрицательный цикл

    return dist

Сложность: O(V·E).

На интервью обычно спрашивают:

• есть ли отрицательные веса,
• нужно ли проверить отрицательные циклы,
• какой стартер (из какой вершины считаете достижимость).

Промежуточные случаи и ловушки

1. “Кратчайший путь в графе с единичными весами, но запрет на посещение вершин”
   Это может сломать простую BFS, если состояние зависит от множества посещённых — тогда графом становится пространство состояний (и число вершин резко растёт).

2. “Кратчайший путь, но требуется восстановить маршрут”
   Тогда нужно хранить parent[to] при обновлениях (в BFS это особенно просто). После вычисления расстояния восстановите путь обратным проходом.

3. “Найти кратчайшие расстояния до всех”
   Для Дейкстры это прямой запрос; для BFS — тоже.

4. Не путать “кратчайший путь по рёбрам” и “по весам”
   BFS решает первое; Дейкстра — второе.

Типовые задачи с собеседований и как их решать

Задача A: “Достижимость и количество шагов”

Пример формулировки: «Дан граф. Сколько минимальных переходов нужно, чтобы попасть из s в t?»

Решение:

• граф без весов → BFS от s,
• dist[t] даст ответ (если -1, значит недостижимо).

Сложность: O(V + E).

Задача B: “Можно ли выполнить все задания?”

Пример формулировки: «Есть список зависимостей. Можно ли выполнить все курсы? Если да — предложите порядок.»

Решение:

• построить ориентированный граф зависимости,
• запустить топологическую сортировку Кана,
• если порядок не покрывает все вершины → цикл → нельзя.

Сложность: O(V + E).

Задача C: “Сколько существует топологических порядков?”

Чаще это не первый вопрос, но встречается. Тут уже BFS/DFS недостаточны напрямую: нужно комбинаторное рассуждение (и обычно NP-трудность в общем случае). На интервью могут дать ограниченный вариант:

• небольшие V,
• или специальная структура.

Важно не “наивно” перебирать — лучше уточнить ограничения и ожидания (часто хотят динамику по состояниям или DP на подмножествах при маленьком V).

Задача D: “Маршрут с минимальной стоимостью”

Пример: «Дан граф дорог с ценой. Найдите минимальную стоимость от s до t.»

Решение:

• если веса неотрицательны → Дейкстра,
• если веса отрицательные → Беллман–Форд (и проверка циклов).

Сложность: по выбранному алгоритму.

Практика оценки корректности: что проверять в решении

На интервью решения чаще всего ломаются не “идеей”, а мелкими деталями. Вот чеклист.

Для BFS

• dist инициализирован корректно (-1 или INF),
• вершина помечается при добавлении,
• очередь корректно хранит вершины,
• не забыли учесть несвязный граф (для “до всех вершин” — это отдельная логика).

Для DFS

• корректная обработка цветового состояния в ориентированном графе при поиске цикла;
• отсутствие чрезмерной рекурсии (если используют Python, рекурсивный DFS может упереться в лимит глубины; итеративный безопаснее);
• корректная работа с несвязным графом (инициализировать обход от всех непосещённых).

Для топологической сортировки

• правильно посчитать in_degree и обновлять его при извлечении вершины;
• правильно проверить len(order) == n.

Для кратчайших путей

• Дейкстра: веса только неотрицательные