Что такое графы в программировании
Перейти к содержимому

Что такое графы в программировании

  • автор:

Графы. Способы представления графа в программе

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

graph_example_circuit_drawing

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

Если направление ребер графа имеет значение (например при отражение отношения вложенности каталогов) – то граф называется ориентированным. Если направление не важно (например при соединении элементов электрической цепи) – граф является неориентированным. Кроме того, ребрам часто приписывается вес, граф в этом случае называется взвешенным – в системе дорог веса ребер могут отражать расстояния между городами.

В связи с этим возникает необходимость обработки графов компьютером, но для этого необходимо сначала каким-то удобным для обработки образом разместить его в памяти. Итак, граф ( G ) – это совокупность вершин ( V ), и дуг ( E ), в зависимости от того, как они задаются, выделяются следующие способы машинного представления графа:

  • матрица смежности для графа из N вершин хранится в виду двумерного массива размером N x N . Вершины графа в этом случае задаются номерами (индексами строк и столбцов матрицы), а ячейка графа matrix[i, j] отражает наличие дуги между соответствующими вершинами. Например, при наличии дуги в ячейке может быть записана единица (или вес ребра i->j для взвешенного графа) , а при отсутствии – ноль;
  • матрица инцидентности для графа из N вершин и M дуг хранится в виде двумерного массива размером N x M . Ячейка матрицы matrix[i, j] отражает инцидентность ребра j вершине i , т.е. тот факт, что это ребро выходит или входит в вершину i . Если ребро не связано с вершиной – в соответствующей ячейке матрицы записывается ноль, в противном случае единица (если граф ориентированный, то начало ребра можно отметить -1 , а конец 1 , если граф взвешенный – единица может быть заменена весом соответствующего ребра).

graph_example

Матрица смежности графа:

A B C D E F G
A 0 12 0 0 0 16 3
B 12 0 8 0 0 0 6
C 0 8 0 4 0 0 8
D 0 0 4 0 14 0 30
E 0 0 0 14 0 28 11
F 16 0 0 0 28 0 13
G 3 6 8 30 11 13 0

Матрица инцидентности графа:

AB BC CD DE EF FA AG BG CG DG EG FG
A 12 0 0 0 0 0 3 0 0 0 0 0
B 12 8 0 0 0 0 0 6 0 0 0 0
C 0 8 4 0 0 0 0 0 8 0 0 0
D 0 0 4 14 0 0 0 0 0 30 0 0
E 0 0 0 14 28 0 0 0 0 0 11 0
F 0 0 0 0 28 16 0 0 0 0 0 13
G 0 0 0 0 0 16 3 6 8 30 11 13

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

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

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

Списки смежности графа:

A B(12) F(16) G(3)
B A(12) C(8) G(6)
C B(8) D(4) G(8)
D C(4) E(14) G(30)
E D(14) F(28) G(11)
F A(16) E(28) G(13)
G A(3) B(6) C(8) D(30) E(11) F(13)

Списки смежности и инцидентности решают проблему расширяемости графа, т.к. новые узлы и дуги могут быть очень просто и эффективно добавлены во время выполнения программы, кроме того они более оптимальны по памяти, т.к. хранятся только данные о существующих дугах. Однако, такой способ представления графа менее эффективен по процессорному времени, т.к. для проверки существования дуги в худшем случае нужно будет перебрать все дуги, выходящие из некоторой вершины, но в матрице смежности было достаточно обратиться к элементу массива (асимптотическая сложность ухудшилась с O(1) до O(K) при использовании связных списков или O(log(K)) при использовании хеш-массивов). Важно, что K в этом случае – количество смежных вершин, для многих графов оно не будет очень большим (например, если граф представлял бы карту города, то скорее всего значение K для каждой вершины не превышало бы 4-6 ), в связи с этим, нужно очень внимательно выбирать структуру данных для хранения списков смежности/инцидентности.

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

struct Node < int value; std::listadj; >

Сам граф в программе хранится в виде списка таких вершин.

Литература по теме:

  • Анализ сложности алгоритмов. Примеры – поможет разобраться с оценкой сложности по памяти и процессорному времени (нужно чтобы уметь выбирать наиболее подходящую для своей задачи структуру данных);
  • Макоха А. Н., Сахнюк П. А., Червяков Н. И. Дискретная математика: Учеб. пособие. – М. ФИЗМАТЛИТ, 2005 – 368 с.
  • Дж. Макконелл Анализ алгоритмов. Активный обучающий подход. — 3-е дополненное издание. М: Техносфера, 2009. -416с.

Практическое применение графов — Алгоритмы на графах

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

Выбираем оптимальный путь на метро

Представьте себе схему метро крупного города: скорее всего, в центре будут пересекаться несколько разных веток. Из-за этого получается, что проехать между станциями можно разными способами.

Например, в московском метро от станции «Фрунзенская» до станции «Полянка» можно доехать двумя способами:

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

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

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

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

Неочевидно, почему используют слово «вес», а не «длительность пути». Этому есть объяснение. За названием «взвешенные графы» скрываются разные задачи, решаемые одним и тем же способом. Для некоторых задач числа обозначают время, для других — расстояния, для третьих — денежные суммы, для четвертых — вес.

Этот термин широко используется в математике — там есть весовые коэффициенты или весовая функция. Так что программисты получили этот термин в наследство от математиков.

Строим маршрут по автомобильным дорогам

Рассмотрим еще одну задачу — построение автомобильного маршрута. Для начала нужно определиться с ребрами и вершинами:

  • Ребрами будут считаться сами дороги
  • Вершинами — развилки и пересечения дорог

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

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

На этот граф мы добавили стрелки, которые показывают направление движения:

  • Если дорога односторонняя, мы рисуем ребро со стрелкой
  • Если дорога двухсторонняя, мы рисуем два ребра с противоположными стрелками

Если у ребер графа задано направление, такой граф называют направленным или ориентированным. Часто название «ориентированный граф» сокращают до «орграфа».

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

Выбираемся из лабиринта

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

В таком случае мы согласимся на любой путь и не будем уточнять, если ли пути покороче.

Есть несколько стратегий выхода из лабиринта. Например, есть правило правой руки, которое предлагает такую стратегию:

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

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

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

Рассмотрим этот рисунок подробнее:

  • Красными линиями обозначены ребра графа
  • Кружками обозначены вершины
  • Направление обхода графа показано синим цветом

Стратегия предполагает, что мы пытаемся пройти как можно глубже, а если попадаем в тупик, возвращаемся назад. На рисунке это тоже видно — синяя линия часто идет в двух направлениях.

Такой способ движения по графу называется обходом в глубину. Этот алгоритм применяется для поиска вершины с определенными свойствами, поэтому часто употребляют похожий термин — «поиск в глубину». В профессиональной литературе вы можете встретить аббревиатуру DFS — depth first search, то есть «поиск сначала в глубину».

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

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

Обходя лабиринт с петлями, можно помечать посещенные развилки мелом. Встретив пометку, мы узнаем, что попали в цикл. Действовать в этом случае надо так же, как и в тупике — развернуться и идти назад.

Обходим препятствия

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

Игровая карта может выглядеть так:

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

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

Представим, что нам надо добраться из вершины Н в вершину К:

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

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

Другое название этого алгоритма — поиск в ширину или BFS, breadth first search. Он позволяет найти маршрут с наименьшим количеством ребер. Впрочем, у него гораздо больше применений. В частности, одна из его модификаций позволяет закрашивать на изображениях замкнутые области произвольной формы.

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

Считаем сдачу

Одна из задач, которую решает программное обеспечение банкоматов и вендинговых аппаратов — выдача сдачи. Как правило, автоматы пытаются выдать сдачу наименьшим количеством банкнот или монет.

Номиналы монет подбираются так, чтобы ими можно было выдать любую сумму. Например, сдачу в 8 рублей можно выдать тремя монетами: 5 рублей, 2 рубля и 1 рубль.

Чтобы посчитать сдачу, можно использовать простой алгоритм выбора монет:

  • Пока можем, набираем сумму самыми крупными монетами
  • Затем переходим к следующим по номиналу монетам, и так далее

Проблема в том, что иногда в автомате заканчиваются монеты определенного номинала. Отсутствие двухрублевых монет не скажется на работе алгоритма: он выберет одну пятирублевую монету и три однорублевых.

Но если в автомате закончатся рублевые монеты, алгоритм не сможет вернуть сдачу в 8 рублей. Сначала он выберет монету в 5 рублей, потом монету в 2 рубля, а дальше начинаются сложности — надо выбрать монету в 1 рубль, а они закончились.

Даже в этом случае задача может быть решена — сдачу можно выдать четырьмя монетами по 2 рубля. Проблема в том, что простой алгоритм этот вариант не найдет.

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

На рисунке мы видим, что каждый узел графа может содержать набор монет. Двигаясь по стрелкам, мы добавляем к набору одну новую монету. Мы начинаем с пустого узла, в котором нет ни одной монеты. Далее мы ищем узлы, где достигается нужная сумма в 8 рублей.

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

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

Хорошим кандидатом для решения задачи о монетах будет алгоритм поиска в ширину. Мы продвигаемся во всех направлениях от пустого узла, в поисках узлов, содержащих сумму 8 рублей.

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

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

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

Выводы

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

  • Находить кратчайшие маршруты на карте метро — решать задачи о кратчайшем пути с помощью взвешенных графов
  • Строить пути на автомобильных картах с помощью ориентированных графов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов

Наши выпускники работают в компаниях:

Что такое графы, и как их применять в аналитике

Графы — это способ аналитики данных. Рассказываем о графовой аналитике, практических решениях и первых шагах для новичков.

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

Аватарка эксперта Владимир Ловцов

Владимир Ловцов
Эксперт-аналитик Группы «Иннотех»

Графы — одна из самых древних структур представления информации. Как только люди научились рисовать кружочки и проводить между ними линии, стало понятно, что таким образом можно представлять связи объектов друг с другом.

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

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

Если углубиться в научные изыскания, то графы — это математические структуры, используемые для изучения парных отношений между объектами. Но гораздо проще представить граф на наглядном примере. Представим, что вам нужно разнести документы по девяти разным кабинетам. Каждый кабинет — это вершина графа, а расстояние между ними — рёбра графа определённой длины (величину длины можно записать цифрой для удобства).

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

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

Что такое графы, и как их применять в аналитике 1

Несмотря на кажущуюся простоту, граф — крутая, но очень сложная структура. Он хранится либо в стандартной двумерном массиве, но так его сложно воспроизвести, либо в специфическом виде в формате json — для таких форматов нужна соответствующая база данных и графовый движок.

Что такое графовая аналитика?

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

Если по-простому, то это связь между двумя сущностями. То есть, даже если ты позвонил себе, то образовался граф. По сути, это дуга, которая ведёт сама к себе.

Под сущностями в графовой аналитике понимаются субъекты или объекты. Например, субъектами могут быть люди — когда человек звонит другому человеку. А можем рассматривать объекты в виде телефонов, на которые поступает звонок.

Где используется графовая аналитика?

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

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

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

Некоторые медицинские и фармакологические компании могут использовать графы для описания химической структуры. Логика тут простая — между атомами всегда есть связь, которая формирует структуру вещества. И вот эти структуры или даже химические связи можно изобразить с помощью графов. По заданным критериям производится поиск химического состава, например, нового лекарства или обезболивающего, которое может быстро действовать без вреда для организма.

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

Компания «Дататех», входящая в группу «Иннотех», разработала платформу графовой аналитики MIRION, позволяющую работать со сложной структурированной и неструктурированной информацией, которая потенциально может иметь какие-то связи. Используемые данные можно визуализировать и решать различные задачи, где можно использовать граф. Например, организовать тот же антифрод, аналитику клиентов, поиск родственников, группы связанных лиц и многое другое. Платформа гибкая и универсальная для работы с большими графами, и да там уже гиперграф.

Насколько перспективна технология?

За графовым анализом будущее. Пользователи постоянно генерируют гигантские объёмы данных. Каждую минуту по всему миру в среднем отправляются 231,4 миллиона писем электронной почты и 16 млн текстовых сообщений. За это же время пользователи Twitter отправляются 347 200 публикаций, а в Snapchat появляются и исчезают 2,43 млн снимков, на YouTube загружают 500 часов видео, в Tinder оценивают 1,1 млн потенциальных партнёров, в Google отправляются 5,9 млн поисковых запросов, а пользователи Zoom проводят 104,6 тысяч часов видеосвязи.

Так как объём данных растёт, то мы получаем множество взаимосвязей. Сервисы видят транзакции пользователя, что происходит у него в телефоне, а это позволяет строить графы, которые дают возможность получить множество сведений о конкретном человеке, здравствуй профиль 365 градусов.

Как правило, у банков лежит множество данных в Data Lake — у кого-то это озёра данных, а у некоторых болота данных. А если к ним добавить информацию от телеком-операторов, ФНС, Мосбиржи и так далее, получается прозрачная картина интересов и потребностей конкретного пользователя.

И на этом современная графовая аналитика не останавливается. С помощью ML удаётся уже предсказывать с заданным уровнем точности поведение человека. Например, что с вероятностью 80% Иван Иванович пойдёт в конкретный магазин и с вероятностью 30% купит определённые продукты. Получается, мы можем заранее предложить Иван Ивановичу то, что нам выгодно в данный момент (берите на вооружение).

Графы также активно применяются для ML. Но этот пункт довольно обширный и достоин отдельной серии статей, которая обязательно появится на площадке.

Какие инструменты используются для графовой аналитики?

Если говорить о языках программирования, то для многих популярных из них уже созданы необходимые библиотеки для работы с графами. Например, для Java — это JGraph и JGraphT, Python — NetworkX и Plolty, С++ — Boost Graph Library.

В распространённом фреймворке Apache Spark для распределённой обработки неструктурированных и слабоструктурированных данных также имеется собственный компонент для работы с графами — GraphX.

Самой распространённой графовой СУБД считается Neo4j. Также используются для работы базы данных MongoDB, Amazon Neptune, ArangoDB, JanusGraph и другие проекты.

Что необходимо для изучения графовой аналитики?

Новички могут изучить базовую теорию графов. Например, прочитать книгу «Введение в теорию графов» авторства Робина Дж. Уилсона.

Так как мы в «Иннотех» используем специфическую базу данных, то проходили обучение по алгоритмам графов на нашей графовой базе данных (ГБД), то есть, что графовые данные из себя представляют, как должны храниться, как обходить граф и так далее. Но это был наш внутренний курс. Всем остальным можно присмотреться к курсам от МФТИ и курсам по конкретным ГБД от их разработчиков.

Математические методы нужны больше специалистам более высокого уровня, например, архитекторам ГБД. Для новичков это сложная и, на самом деле, не нужная для начала проекта тема — хватит и парочки статей из «Википедии».

Аналитикам, которые хотят начать использовать графы, стоит задаться вопросом, а зачем это им нужно. Надо понимать, что на рынке больше востребованы аналитики широкого профиля: системные, бизнес- и фулстек-аналитики, а также дата-аналитики и Data Scientist. Графовая аналитика больше заточена под конкретные проекты и специалист по ней порой весьма узкоспециализирован. Однако обладает отличными знаниями и дорогой экспертизой, потому что может с нуля построить правильные процессы по применению графовой парадигмы в компании и на проекте.

Графы: основы теории, алгоритмы поиска

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

Одной из важнейших составляющих спортивного программирования является изучение алгоритмов. В этой статье мы охватим большое количество алгоритмов, в том числе все алгоритмы на графах, знание которых понадобится вам для успешного решения задач из теории графов на соревнованиях по программированию. Конечно, одних теоретических знаний алгоритмов недостаточно, и вам придётся набить руку в решении практических задач на таких сайтах, как Codeforces. Настоящая же статья представит вам инструменты, необходимые для освоения важных графовых алгоритмов. Итак, приступим.

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

Графы, в понимании программистов, — это не те графики, которые мы изучали в школе. Это не столбиковые диаграммы или гистограммы.

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

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

Вот список всех терминов, относящихся к теории графов, которые вам нужно знать:

  • путь — последовательность рёбер, соединяющая разные (неповторяющиеся) вершины;
  • маршруты — это те же пути, только они не требуют последовательности разных вершин;
  • цикл — группа вершин, связанных вместе в замкнутую цепь. На рисунке выше вершины [1,2,4] составляют цикл;
  • связный граф — граф, в котором между любой парой вершин имеется один путь;
  • дерево — связный граф, не содержащий цикла;
  • неориентированный граф — граф, в котором рёбра не имеют направления. На рисунке выше показан как раз неориентированный граф. В таком неориентированном графе можно перемещаться вдоль ребра в любом из двух направлений;
  • ориентированный граф — граф, в котором рёбра имеют направления и обозначаются стрелками. В таком ориентированном графе можно перемещаться вдоль ребра только в указанном направлении.

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

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

Будут показаны два способа представления графов: матрицы смежности и списки смежности. Больше вам пригодится представление графов в виде списка смежности.

Матрицы смежности

Матрица смежности представляет собой граф в виде двумерной матрицы с размерами V x V, где V — количество вершин графа. Матрицы смежности лучше всего применять, когда V² примерно равно E (числу рёбер), то есть когда граф плотный. Запись a_ij обозначает, сколько рёбер соединяют вершину i и вершину j.

Код:

Следующий код используется для создания матрицы смежности неориентированного графа. Чтобы код создавал матрицу смежности для ориентированного графа, измените функцию add_edge , удалив вторую строку внутри неё: matrix[v][u] = 1;

#include
using namespace std;
int matrix[20][20]; //матрица смежности изначально 0
int count = 0;
//следующая функция используется для вывода
void displayMatrix(int v) int i, j;
for(i = 0; i < v; i++) for(j = 0; j < v; j++) cout >
cout >
>
void add_edge(int u, int v) < //функция добавления ребра в матрицу
matrix[u][v] = 1;
matrix[v][u] = 1;
>
main(int argc, char* argv[]) int v = 6; //в графе 6 вершин
add_edge(0, 4);
add_edge(0, 3);
add_edge(1, 2);
add_edge(1, 4);
add_edge(1, 5);
add_edge(2, 3);
add_edge(2, 5);
add_edge(5, 3);
add_edge(5, 4);
displayMatrix(v);
>

Списки смежности

Другой распространенный способ представления графов в коде — списки смежности. Суть в том, что вы создаёте списки соседей для каждой вершины, а затем помещаете все эти списки в другой список. Их лучше всего применять, когда в графе небольшое количество рёбер, то есть когда граф разрежённый. Если у вас взвешенный граф, т.е. каждое ребро графа имеет какой-то вес, то в списке будут содержаться пары для рёбер (сосед, вес).

Код:

#includeusing namespace std;void addEdge(vector adj[], int u, int v) adj[u].push_back(v); 
adj[v].push_back(u);//удаляем эту строку для ориентированных графов
>int main() int v = 5; //5 вершин
vector adj[v];
addEdge(adj, 0, 1);
addEdge(adj, 0, 4);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
>

Поиск в глубину

Теперь, когда мы научились представлять графы в коде, можем приступить к изучению некоторых алгоритмов на графах! Начнём с поиска в глубину (DFS) и завершим поиском в ширину (BFS). Чтобы не загромождать статью, алгоритмы поиска пути не будут здесь рассматриваться (интересующиеся могут ознакомиться с алгоритмом поиска кратчайшего пути Беллмана-Форда).

Поиск в глубину — это один из базовых алгоритмов на графах. Он применяется для поиска расстояния от одной вершины до других вершин в графе. Это алгоритм обхода.

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

  1. Помещаем любую из вершин графа на стек.
  2. Берём элемент со стека и добавляем его в список посещённых.
  3. Создаём список соседей этой вершины. Добавляем в стек те, что не находятся в списке посещённых.
  4. Повторяем 2 и 3 пункты, пока стек не опустеет.

Код:

#include using namespace std;const int N = 100000;
vector adj[N];
bool visited[N];
void dfs(int s) if (visited[s]) return;
visited[s] = true;
for (auto u: adj[s]) dfs(u);
>
>

Поиск в ширину

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

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

  1. Помещаем любую вершину в графе в конец очереди.
  2. Берём элемент в начале очереди и добавляем его в список посещённых.
  3. Создаём список соседей этой вершины. Добавляем в конец очереди непосещённые.
  4. Повторяем 2 и 3 пункты, пока очередь не опустеет.

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

Код:

// Быстрая реализация алгоритма поиска в ширину с использованием
// векторов и очереди
#include
#define pb push_back
using namespace std;vector v;
vector > g;
void edge(int a, int b) g[a].pb(b);
// для неориентированного графа добавляем эту строку
// g[b].pb(a);
>
void bfs(int u) queue q;
q.push(u);
v[u] = true;
while (!q.empty()) int f = q.front();
q.pop();
// Ставим в очередь все соседние F и помечаем их как посещённые
for (auto i = g[f].begin(); i != g[f].end(); i++) if (!v[*i]) q.push(*i);
v[*i] = true;
>
>
>
>

Заключение

Освоив теоретическую часть, касающуюся двух самых важных алгоритмов обхода на графах, вам остаётся только практиковаться, чтобы использовать эти алгоритмы в соревнованиях по программированию. Я бы порекомендовал для начала Codeforces: решайте задачи, помеченные тегами bfs и dfs с рейтингом до 1400. Когда почувствуете, что справляетесь с ними, увеличьте сложность.

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

  • Как создавать анимированные графы в Python
  • Графы и пути: Алгоритм Брона-Кербоша, максимальные группы
  • Гравафы и пути — алгоритм Дейкстры

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *