Графы: представление и обход

В задаче дана таблица, где строки и столбцы пронумерованы от одного до пяти, и рисунок графа с вершинами-буквами. Нужно узнать, какому номеру таблицы соответствует буква «Д». Ученик смотрит на рисунок, находит дорогу длиной семь, ищет семёрку в таблице и обнаруживает три подходящих клетки. Он выбирает одну по наитию. Начинать же надо с того, что от нумерации не зависит. Число дорог, выходящих из вершины, на рисунке видно сразу, а в таблице это количество заполненных клеток в строке. Если у «Д» четыре дороги и только в одной строке четыре числа, то соответствие найдено, и семёрки вообще не понадобились.

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

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

Как записывают граф

Один и тот же граф хранится по-разному, и выбор определяется тем, что с ним будут делать. Матрица смежности — таблица, где на пересечении строки и столбца стоит число: единица, если ребро есть, и ноль, если нет, а для взвешенного графа вместо единицы пишут вес. У неориентированного графа матрица симметрична, у ориентированного нет. Узнать по матрице, соединены ли две вершины, можно за один шаг, но память растёт пропорционально квадрату числа вершин, и граф из ста тысяч вершин в матрицу не поместится.

Список смежности хранит для каждой вершины только её соседей. В Python его удобно держать в словаре, где ключ — номер вершины, а значение — список соседей: graph = {1: [2, 3], 2: [4], 3: [4], 4: []}. Обходить такой граф быстро, потому что от вершины сразу видно, куда идти. Третий способ, список рёбер, просто перечисляет пары вершин и чаще всего встречается в файле: именно в таком виде данные приходят на вход. Из списка рёбер словарь смежности собирается циклом в три строки, и такую сборку стоит отработать раньше всего остального.

Для взвешенного графа в словаре вместо одного номера хранят пару: graph = {1: [(2, 5), (3, 1)], 2: [(4, 2)]}. Первое число пары означает соседа, второе длину ребра. Так надёжнее, чем матрица с весами: в ней ноль может означать и «ребра нет», и «длина ноль», а пара с именем соседа таких вопросов не вызывает.

Типичная ошибка при сборке происходит с неориентированным графом. Ребро между первой и второй вершинами записывается как «из первой во вторую», а обратное направление забывается. Программа не падает, ответ получается, но обход зависит от того, с какой вершины стартовать, и ученик ищет ошибку в самом обходе, хотя она в данных. Привычка после сборки напечатать словарь для маленького графа и сверить с рисунком отнимает полминуты и экономит час.

В глубину и в ширину

Оба обхода посещают все вершины, достижимые из стартовой, и различаются порядком. Обход в ширину берёт вершины слоями: сначала все соседи старта, потом соседи соседей, и так далее. Для этого нужна очередь, в Python её роль играет deque из модуля collections, потому что обычный список плохо удаляет элементы с начала. Обход в глубину идёт по одной цепочке до тупика, потом возвращается и пробует другую; естественная запись — рекурсия или стек.

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

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

Второе место связано с рекурсией. Стандартный предел глубины вызовов в Python около тысячи, и обход в глубину по цепочке из ста тысяч вершин упирается в него с ошибкой RecursionError. Это особенность языка, а не ваша ошибка. Выходов два: поднять предел функцией setrecursionlimit или заменить рекурсию явным стеком. Какой лучше, зависит от того, на чём вы будете писать, и это стоит выяснить до экзамена, а не на нём. Рекурсию как приём разбирает отдельная статья, рекурсия на простых примерах.

Задачи про число путей

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

Маленький пример на четырёх вершинах: из А стрелки в Б и В, из Б стрелки в В и Г, из В стрелка в Г. Для А число путей равно единице, для Б единице, для В двум (из А напрямую и через Б), для Г трём: сумма значений Б и В. Все три пути выписываются руками, и совпадение с суммой убеждает лучше любой формулы.

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

Откуда берётся навык и куда он ведёт

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

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

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

Когда обход графа остаётся непонятным

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

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

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

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

Как заниматься онлайн

Графы проще всего объяснять на доске, и вот её-то на платформе и нет, как нет и показа экрана. Выручает лист бумаги: ученик рисует вершины и стрелки сам, поднимает лист к камере, а репетитор говорит, какое ребро лишнее или куда не хватает стрелки. Код он на вашем экране не увидит и получит его текстом в чат; одно сообщение вмещает до 4000 знаков, обход графа с вводом и выводом укладывается. Чат появляется, как только репетитор получил ваш контакт. Сами занятия не записываются, поэтому разобранный пример лучше сразу переписать в тетрадь.

Начать поиск:

• репетиторы по информатике
• репетиторы по информатике для подготовки к ЕГЭ
• репетиторы по информатике с пробным уроком
• репетиторы по информатике для 10–11 класса

Вопросы и ответы

Нужно ли знать алгоритм Дейкстры? Для школьной программы и первой части экзамена обычно нет. Для олимпиад и углублённого курса знать надо.

Что выбрать, матрицу или словарь? Словарь списков для обхода, матрицу для проверки наличия ребра и для небольших графов. Если не уверены, начните со словаря: он ближе к тому, что вы потом будете читать из файла, и редко подводит на больших данных. Переходить на матрицу имеет смысл, когда нужно часто отвечать на вопрос «соединены ли эти две вершины», и вершин немного.

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

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