Графы. Алгоритмы обхода графа (BFS, DFS): ЕГЭ по информатике

Графы — это структура из вершин и рёбер. Обход графа (BFS — поиск в ширину, DFS — поиск в глубину) позволяет систематически посещать все вершины. На ЕГЭ по информатике задачи на графы встречаются в заданиях на анализ информационных моделей (обычно №1, №13, №18 в разных годах), где нужно найти…

Что нужно знать

• Граф состоит из вершин (узлов) и рёбер (связей). Рёбра могут быть направленными (ориентированный граф) или ненаправленными.
• Смежность вершин — наличие ребра между ними. Матрица смежности — таблица N×N, где 1 означает наличие ребра, 0 — отсутствие. Список смежности — для каждой вершины перечислены соседние.
• BFS (поиск в ширину) обходит граф по уровням: сначала все соседи начальной вершины, затем соседи соседей и т.д. Использует очередь. Находит кратчайшие пути в невзвешенном графе.
• DFS (поиск в глубину) идёт как можно глубже по одной ветви, затем возвращается. Использует стек или рекурсию. Применяется для проверки связности, поиска циклов, топологической сортировки.
• Оба алгоритма имеют сложность O(V + E), где V — число вершин, E — число рёбер.
• В ЕГЭ часто требуется найти количество путей из одной вершины в другую (динамическое программирование по графу) или кратчайший путь (алгоритм Дейкстры для взвешенных графов, но BFS — для невзвешенных).

Термины и понятия

• Граф: совокупность вершин и соединяющих их рёбер.
• Ориентированный граф (орграф): граф, в котором рёбра имеют направление (дуги).
• Невзвешенный граф: граф, где все рёбра имеют одинаковый вес (обычно 1).
• Взвешенный граф: граф, каждому ребру которого сопоставлено число (вес).
• Смежные вершины: две вершины, соединённые ребром.
• Матрица смежности: квадратная матрица размера V×V, где элемент a[i][j] = 1, если есть ребро из i в j, иначе 0.
• Список смежности: структура данных, где для каждой вершины хранится список её соседей.
• BFS (Breadth-First Search, поиск в ширину): алгоритм обхода графа, при котором вершины посещаются в порядке возрастания расстояния от…

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

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

Как пройти тему

В курсе «Информатика» тема «Графы. Алгоритмы обхода графа (BFS, DFS)» занимает 2 занятия по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Другие темы раздела

• Понятие алгоритма. Свойства алгоритмов. Способы записи
• Базовые алгоритмические конструкции: следование, ветвление, цикл
• Вспомогательные алгоритмы. Рекурсия
• Анализ алгоритмов. Определение результата работы алгоритма
• Поиск ошибок в алгоритмах. Отладка
• Обработка одномерных массивов: поиск, сортировка, статистика

← Предыдущая тема: Структуры данных: стеки, очереди, списки, деревья
Следующая тема: Алгоритмы поиска кратчайших путей (Дейкстра, Флойд)

Все темы: ЕГЭ по информатике