Шпаргалка: графы и обходы

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

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

Граф состоит из вершин и рёбер. Вершины обозначают объекты: города, станции, компьютеры или клетки поля. Рёбра показывают связи между ними: дороги, кабели, маршруты. Если направление важно, ребро изображают стрелкой, и граф называют ориентированным. Если можно двигаться в обе стороны, граф неориентированный.

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

Вершина: объект
Ребро: связь между объектами
Степень вершины = число инцидентных рёбер
Путь: последовательность вершин, соединённых рёбрами

Граф удобно задавать рисунком, списком рёбер, матрицей смежности или списками смежности. В задачах ЕГЭ и ОГЭ одна и та же сеть может быть представлена по-разному, поэтому сначала определи, что является вершинами, а что — связями.

Как читать представление графа

Список рёбер перечисляет пары связанных вершин. Например, запись А—Б означает связь между А и Б. В ориентированном графе запись А → Б означает движение только из А в Б. Если граф взвешенный, рядом указывают вес: А—Б, 7.

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

Представление	Что показывает	Когда удобно
Рисунок	Вершины и связи наглядно	Для коротких путей и компонентов
Список рёбер	Все пары связанных вершин	Для подсчёта и построения
Матрица	Есть ли связь каждой пары	Для таблиц и проверки смежности
Списки смежности	Соседей каждой вершины	Для обходов графа

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

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

Обход в ширину

Обход в ширину, или BFS, исследует граф слоями. Сначала посещается стартовая вершина, затем все её соседи, потом соседи этих вершин. Для запоминания представь волну, расходящуюся по воде. Главный инструмент BFS — очередь: первый добавленный элемент обрабатывается первым.

Алгоритм начинается с отметки стартовой вершины. Её помещают в очередь. Пока очередь не пуста, берут первую вершину, просматривают её соседей и добавляют в очередь тех, кто ещё не посещён. Каждую вершину важно отмечать в момент добавления, иначе её можно положить в очередь несколько раз.

Старт → соседи старта → вершины на расстоянии 2 → вершины на расстоянии 3

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

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

Обход в глубину

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

Начни со стартовой вершины, отметь её и перейди к непосещённому соседу. Повторяй шаг, пока из текущей вершины есть новый сосед. Если новых соседей нет, возвращайся к предыдущей вершине. Обход завершается, когда проверены все возможные возвраты.

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

DFS: выбрать → углубиться → упереться в конец → вернуться → выбрать следующую ветвь

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

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

Разобранный пример и ошибки

Рассмотрим неориентированный граф с рёбрами А—Б, А—В, Б—Г, В—Д, Г—Е, Д—Е. Выполним BFS из вершины А, просматривая соседей в алфавитном порядке.

1. В очередь помещаем А: посещённые А
2. Обрабатываем А, добавляем Б и В: очередь Б, В
3. Обрабатываем Б, добавляем Г: очередь В, Г
4. Обрабатываем В, добавляем Д: очередь Г, Д
5. Обрабатываем Г, добавляем Е: очередь Д, Е
6. Обрабатываем Д: Е уже посещена
7. Обрабатываем Е: новых вершин нет
Порядок BFS: А, Б, В, Г, Д, Е
Расстояния от А: А — 0, Б и В — 1, Г и Д — 2, Е — 3

Типичная ошибка — считать вершину посещённой только после обработки. Правильнее отмечать её сразу при добавлении в очередь или стек. Ещё одна ловушка — игнорировать направление стрелок. Переход А → Б не означает автоматически переход Б → А.

Перед решением подчеркни в условии слова «направленный», «взвешенный», «кратчайший», «все вершины» и «число рёбер». Они подсказывают нужный метод.

Что запомнить

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

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

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