Обход графа

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

1. читать и строить представления графа (матрица и списки смежности),

2. корректно реализовывать DFS (поиск в глубину) и BFS (поиск в ширину),

3. доказывать корректность на уровне инвариантов и оценивать сложность,

4. применять правила обхода при решении экзаменационных задач с таблицами и списками рёбер,

5. избегать типичных ошибок (неправильная инициализация, забытые метки, неверный учёт ориентированности).

Математическая модель и представления

Основные определения

Представления графа

Выбор представления: для разреженных графов (типично в КИМ) – списки смежности. Для задач с матрицами смежности (подсчёт путей фиксированной длины) – матрица.

Поиск в ширину (BFS)

1. Идея и назначение
   

   BFS «растёт» волнами от стартовой вершины s, посещая сначала все вершины на расстоянии 1, затем 2 и т.д. В невзвешенном графе BFS строит дерево кратчайших путей от s: глубина вершины равна длине кратчайшего пути в рёбрах.

2. Инварианты и корректность
   

   • Инвариант очереди: все вершины в очереди упорядочены по невозрастающим расстояниям; при извлечении вершины u её расстояние dist[u] минимально среди непроцессированных.

   • Метка visited (или color) гарантирует, что каждая вершина ставится в очередь не более одного раза.

3. Псевдокод (списки смежности)
   

   BFS(G, s):

       for v in V:

           visited[v] ← false

           dist[v] ← +∞

           parent[v] ← ⊥

       visited[s] ← true

       dist[s] ← 0

       Q ← пустая очередь

       push(Q, s)

       while Q не пуста:

           u ← pop(Q)

           for каждый сосед v из Adj[u]:

               if not visited[v]:

                   visited[v] ← true

                   dist[v] ← dist[u] + 1

                   parent[v] ← u

                   push(Q, v)

   Сложность: O(n+m) при списках смежности.

4. Свойства   
   

   • Для любого v достижимого из s построенный путь (по parent) – кратчайший по числу рёбер.

   • В неориентированном графе дерево BFS минимизирует глубину всех достижимых вершин.

   • Порядок прохода соседей при равных длинах зависит от порядка в списке смежности; для детерминизма на ЕГЭ удобно сортировать соседей по возрастанию номера.

Поиск в глубину (DFS)

1. Идея и назначение
   

   DFS углубляется максимально далеко по одному пути, затем откатывается (backtrack) и ищет альтернативы. Применения: проверка связности, выделение компонент связности, обнаружение циклов, топологическая сортировка ориентированных ацикличных графов (DAG), классификация рёбер.

2. Метки времени и классификация рёбер
   

   В DFS удобно вести времена входа/выхода tin[v] и tout[v]. В ориентированном графе рёбра классифицируются:

   • деревянные (tree): ведут к ещё не посещённой вершине;

   • обратные (back): указывают на активного предка → цикл;

   • прямые (forward) и поперечные (cross) – к уже завершённым вершинам (в ориентации это уточняется по временам).

3. Псевдокод (рекурсивный)
   

   time ← 0

   DFS(G):

       for v in V:

           color[v] ← WHITE

           parent[v] ← ⊥

       for v in V по возрастанию:

           if color[v] = WHITE:

               DFS-Visit(v)

   DFS-Visit(u):

       color[u] ← GRAY

       tin[u] ← ++time

       for v in Adj[u]:

           if color[v] = WHITE:

               parent[v] ← u

               DFS-Visit(v)      # ребро (u,v) – деревянное

           else if color[v] = GRAY:

               # (u,v) – обратное, найден цикл в ориентированном графе

           else:

               # color[v] = BLACK → прямое или поперечное ребро

       color[u] ← BLACK

       tout[u] ← ++time

   Сложность: O(n+m) при списках смежности.

4. Следствия и применения
   

   • Компоненты связности (неориентированный): достаточно запустить DFS от каждой непосещённой вершины; количество запусков = число компонент.

   • Топологическая сортировка (DAG): порядок убывания touttouttout – корректная топологическая нумерация. Наличие обратного ребра в ориентированном графе ⇒ цикл ⇒ топологической сортировки нет.

   • Дерево обхода: совокупность всех деревянных рёбер формирует лес/дерево DFS.

Выбор алгоритма и детерминизм обхода

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

Правило детерминизма (для ЕГЭ): если порядок обхода важен, заранее фиксируйте правило: «соседей посещаем по возрастанию номера» (или лексикографически по имени). Это исключает неоднозначность ответов.

Оценки, корректность, типичные ошибки

1. Оценки
   
   

2. Инварианты корректности
   

   • BFS: если вершина впервые помещена в очередь с расстоянием k, никакой более короткий путь к ней уже не существует (иначе она оказалась бы в очереди раньше).

   • DFS: вершина помечается GRAY при входе и BLACK при выходе; обратное ребро на GRAY фиксирует цикл.

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

   1. Забыли инициализировать visited/color → многократные посещения.

   2. Смешали ориентированность: для неориентированного графа каждое ребро присутствует в обоих списках; в DFS важно не трактовать второе направление как обратное ребро цикла.

   3. Необработанные изолированные вершины: обход только из заданного источника не «видит» другие компоненты.

   4. Нестабильный порядок соседей → непредсказуемый порядок ответа; фиксируйте правило сортировки.

   5. Неправильно подсчитанный уровень в BFS (ошибка при инкременте dist).

   6. Рекурсивный DFS без контроля глубины стека для очень больших графов – возможен переполнение стека; на ЕГЭ масштаб обычно безопасен, но правило стоит знать.

Практические паттерны для задач ЕГЭ

• Подсчёт компонент: многократный запуск DFS/BFS; количество запусков = число компонент; параллельно можно заполнять номер компоненты.

• Кратчайшие пути (невзвешенный): один запуск BFS от источника; расстояния – dist[], пути – через parent[].

• Маршрут/порядок обхода: задайте фиксированный порядок соседей; выпишите точную последовательность посещений.

• Топологический порядок: DFS с запоминанием порядка выхода (или итеративный алгоритм Кана с очередью вершин нулевой полустепени захода).

• Матрицы смежности: степень матрицы A^k даёт число путей длины k между парами вершин (теоретический приём; в КИМ иногда встречаются мини-задачи на k=2,3).

Пять упражнений (академический формат «теория + практика»)

Упражнение 1. Детерминированный порядок DFS

Дан ориентированный граф на вершинах 1..71..71..7. Списки смежности (каждый список – уже отсортирован по возрастанию):
1: 2, 4
2: 5
3: 2, 4, 6
4: 5
5: 7
6: 4, 7
7: –
Требуется:
a) Выполнить полный DFS по порядку вершин 1,2,…,7 (если вершина ещё белая – запускать DFS-Visit). Записать времена tin/touttin/touttin/tout для каждой вершины.
b) Классифицировать рёбра (деревянные, обратные, прямые/поперечные).
c) Сообщить, есть ли цикл (обоснование через наличие обратного ребра).

Упражнение 2. BFS и кратчайшие пути

Дан неориентированный граф на вершинах A,B,C,D,E,FA,B,C,D,E,FA,B,C,D,E,F со списками смежности:
A: B, C
B: A, D, E
C: A, D
D: B, C, F
E: B
F: D
Требуется:
a) Запустить BFS из AAA. Выписать dist[] и parent[] для всех вершин при условии, что соседи просматриваются по алфавиту.
b) Восстановить кратчайшие пути A→EA\to EA→E и A→FA\to FA→F.
c) Построить дерево BFS (указать рёбра дерева).

Упражнение 3. Компоненты связности и изолированные вершины

Дан неориентированный граф на вершинах 1..101..101..10 с рёбрами: {1,2},{2,3},{4,5},{6,7},{7,8}.
Остальные вершины не имеют рёбер.
Требуется:
a) Определить количество компонент связности и перечислить вершины каждой компоненты.
b) Указать, какие вершины изолированы.
c) Сформулировать алгоритм (на уровне псевдокода) для нумерации компонент связности с помощью DFS.

Упражнение 4. Топологическая сортировка или цикл?

Дан ориентированный граф зависимостей (курсы → курсы-последователи):
Alg → DS,
DS → ML,
Math → ML,
ML → Project,
Project → –,
Security → –,
DS → Security.
Требуется:
a) Выполнить топологическую сортировку (любой корректный порядок) и объяснить выбор.
b) Преобразовать один из рёбер так, чтобы появился цикл; указать, какое ребро добавили и как DFS обнаружит цикл (через обратное ребро).
c) Объяснить, почему в присутствии цикла корректного топологического порядка не существует.

Упражнение 5. Матрица смежности и количество путей фиксированной длины

Дан ориентированный граф на вершинах 1..4 с матрицей смежности 

Заключение

Алгоритмы BFS и DFS образуют фундаментальный инструментариум для анализа графов. Их корректность опирается на чёткие инварианты (уровни для BFS, времена и цвета для DFS), а эффективность – на адекватное представление графа и детерминированный порядок обработки соседей. Для ЕГЭ ключевые навыки включают: перевод текстового описания в списки смежности/матрицы, аккуратную трассировку прохода, построение деревьев обхода и вывод строгих свойств (связность, кратчайшие пути, топологические порядки). Освоив правила и практические паттерны, вы превращаете графовые задачи в последовательность формальных шагов – именно это обеспечивает точность и высокие результаты на экзамене.