Не понимаю графы

Что такое граф и почему он кажется сложным

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

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

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

Основные понятия: степень, путь и цикл

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

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

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

Как хранить граф в таблице и списке

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

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

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

Обозначим граф с вершинами A, B и C и рёбрами A—B, A—C. Его список смежности выглядит так:

A: B, C
B: A
C: A

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

Обход графа: поиск в ширину и глубину

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

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

Рассмотрим граф:

1: 2, 3
2: 1, 4
3: 1, 5
4: 2
5: 3

Стартуем из вершины 1. В очередь попадает 1, затем её соседи 2 и 3. После этого рассматриваем 2 и добавляем 4, затем рассматриваем 3 и добавляем 5. Порядок посещения: 1 → 2 → 3 → 4 → 5. Расстояния от 1: до 1 — 0, до 2 и 3 — 1, до 4 и 5 — 2.

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

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

Задача: в неориентированном графе нужно определить, существует ли путь из вершины 1 в вершину 6. Рёбра заданы парами: 1—2, 1—3, 2—4, 3—5, 5—6.

Старт: 1
Соседи 1: 2, 3
Сосед 2: 4
Сосед 3: 5
Сосед 4: нет новых вершин
Сосед 5: 6
Вывод: путь существует: 1 → 3 → 5 → 6

Сначала создаём список смежности. Затем запускаем BFS из 1 и кладём её в очередь. Помечаем 1 посещённой. Из 1 попадаем в 2 и 3, из 3 — в 5, а из 5 — в 6. Как только 6 найдена, можно остановиться: достижимость доказана. Если очередь закончилась, а 6 не отмечена, пути нет.

Первая типичная ошибка — считать длиной пути число вершин. В маршруте 1 → 3 → 5 → 6 четыре вершины, но три ребра. Вторая — забыть направление стрелок. В ориентированном графе переход A → B не означает переход B → A. Третья — не отмечать посещённые вершины. Четвёртая — использовать BFS для взвешенных рёбер с разными весами: обычный BFS подходит для одинаковой стоимости, а не для произвольных весов.

После разбора можно закрепить навык в личном кабинете с бесплатными заданиями, а затем посмотреть подборки по ОГЭ или ЕГЭ.

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

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

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

Следующий шаг простой: зарегистрируйся и реши 5 заданий бесплатно в личном кабинете. После каждого решения объясни себе, почему выбран именно этот обход и что обозначает каждая вершина.