Наука о данных

Теория графов в кратком и практичном изложении

23.09.2020

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

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

Мышление на основе графов/узлов и подходы к решению задач поиска.
Реализация графа с помощью ООП.
Различные представления графов: списки и матрицы смежности.
Типы графов и их реализации: (не)ориентированные, (не)взвешенные графы, а также (а)циклические графы.
Алгоритм Дейкстры, его слабые места и альтернативы.
Области применения теории графов.
Ключевые моменты.

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

Рассмотрим в качестве примера следующую задачу поиска и представим ее как ненаправленный и невзвешенный граф.

У вас имеется висячий замок с двумя колесиками, на которых изображены цифры, инициализированные как 00. Каждым движением вы можете прокручивать одно из колесиков вверх или вниз на один шаг. Поскольку они круглые, то при прокрутке 0 вверх получаем 1, а при прокрутке вниз — 9. Существуют “мертвые комбинации”, набрав значение которых, мы заблокируем замок навсегда. Нужно найти минимальное число движений, необходимых для достижения целевой комбинации, не заблокировав замок, если такое вообще возможно.

Мертвые комбинации: [10, 90, 12], целевая: 11.

Сначала мы создаем “корень” или “голову” графа, которые необходимы в сценариях, где нам нужно генерировать граф по мере продвижения. Им будет ‘00’, иначе называемый корневым кейсом, от которого пойдет дальнейшее ветвление.

Четырьмя соседями узла ‘00’ будут ‘01’, ‘10’, ‘90’ и ‘09’, соответствующие различным комбинациям перемещаемых вверх и вниз колесиков. Теперь в нашем графе есть уже пять узлов и четыре ребра.

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

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

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

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

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

Например, каждый элемент приведенного ниже графа можно представить в коде как отдельный Node. Все они соединены друг с другом через своих Neighbors (соседей). Если мы вызовем, например, NodeA.Neighbors[1].Neighbors[1].Value, то в ответ получим 2. Так произойдет, потому что второй индекс соседей Node A — это Node C, а второй индекс соседей Node C — это Node B, чье значение 2. Такой вид простой связи позволяет легко выполнять обход графа.

Пояснение: ‘A 1’ означает, что Node A имеет значение 1

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

Если поставить задачу обойти граф по соседям и закончить в Node С или Node F, то мы застрянем, потому что у этих узлов нет соседей, а значит и исходящих направлений.

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

V = [A, B, C, D, E, F]
E = [AB, AC, BC, CF, CE, DF, EA, FB, FD]

В этом примере v объявляет существующие узлы, а E объявляет ребро, ведущее от одного узла к другому (AC означает A→C). Поскольку это компактная и простая нотация, графы зачастую представляют именно таким способом.

Иначе его можно написать в виде словаря (карты), в котором ключом будет стартовый узел, а его значением список элементов, на которые он указывает.

adj_l = {A:[B,C], B:[C], C:[F,E], D:[F], E:[A], F:{B,D]}

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

Например, внутри завершенного циклического графа A→B→C→D→A является четырехцикловым графом, а E→F→G→E трехцикловым. Менее очевидным будет другой четырехцикловый граф B→E→F→G→B.

Конкретные виды циклов внутри циклических графов или другие компоненты внутри графов, в которых каждый узел соединен с каждым другим узлом, называются компонентой сильной связности. Например, E→F→G→E — это компонента сильной связности, потому что каждый из узлов [E, F, G} имеет путь к другому независимо от направления. B→E→F→G→B также является сильно связанной компонентой. С другой стороны, A→B→C→D→A не является таковым, потому что в нем нет связи между компонентами B и D.

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

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

Как вариант кратчайшим путем от S→E будет S→D→F→E, для чего потребуется пройти всего три ребра. Тем не менее этот маршрут пролегает по очень узенькой и людной улице. В качестве альтернативы можно рассмотреть путь S→A→B→C→E, который проходит уже через четыре ребра, но большая часть пути представлена шоссе, и итоговые затраты снижены. Когда в граф добавляются примечания расстояния и затрат, он становится взвешенным.

Чтобы реализовать это в нашем фреймворке, можно включить для каждого элемента в Neighbors число, описывающее затраты для достижения данного соседа. Эту информацию можно хранить, к примеру, в кортежах [(n, c), (n, c)], где n представляет узел, а c представляет затраты.

Зачастую графы будут также представлены в виде матрицы, известной как “матрица смежности”. Она уже не так компактна, как список смежности, но может представлять взвешенные графы более естественно. В матрице каждый ряд и столбец представляют узел, а ячейка, расположенная в (x, y), представляет ребро y→x (или наоборот, все зависит от нотации). Если ребра нет, значением будет 0. Если есть, значение будет представлять затраты этого ребра.

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

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

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

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

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

Рассмотрите в качестве примера сеть узлов, где обход каждой связи подразумевает одинаковые затраты. Алгоритм Дейкстры, имеющий небольшие вариации в зависимости от реализации, будет производить поиск по всем легким узлам, пока не достигнет конечного узла E. Это все равно, что вылить ведро воды в месте расположения узла S в надежде, что в итоге она достигнет целевого узла.

Алгоритм A* и многие другие варианты учитывают эти слабые места и в целях улучшения обхода графа добавляют такие расширения, как усиленная память и направление. Центральной точкой применения новейших методов высокоэффективного обхода графа является машинное обучение, а в частности обучение с подкреплением. В данном виде обучения вероятности и состояния представлены в виде графов, обходимых агентом.

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

Применение теории графов в компьютерной науке включает такие варианты:

Моделирование сложных сетей, наподобие социальных, или симуляция заболеваний, наподобие коронавируса. Каждый узел может представлять человека или популяцию, а ребра могут представлять вероятность/легкость передачи. В данной модели мы можем попытаться определить или сформировать круговые замкнутые графы.
Организация и любые иерархические структуры. Графы не обязательно должны представлять циклы и быть циклическими — они также могут выражать иерархию. Например, если вы создадите API для локальной библиотеки, чтобы получать доступ к книгам по их содержанию, то построите для этого граф. Если вы захотите создать карту сайта, то также используете граф. Графовые базы данных — это типы БД, которые хранят данные, опираясь на организованные в графах иерархии.
Любая задача, подразумевающая перемещение агента между множеством локаций или состояний, чаще всего успешно представляется в виде графа. Графы помогают уменьшить сложность практически любой задачи в программировании.
Сервисы вроде Google Maps, которые сообщают вам наилучший маршрут с учетом не только расстояния, но также и времени движения, высоты, платных дорог и т.д. По-сути, они находят наилучший путь в массивном взвешенном графе — представьте узлы, расположенные через каждые пару метров и граф, охватывающий всю Землю.
Теория графов применялась в доказательстве теоремы о четырех красках, которая стала первым принятым математическим доказательством, выполненном на компьютере.
В подразделе МО, именуемом обработкой естественного языка, который занимается моделированием языка, взвешенные представления графов слов и текста чрезвычайно важны, поскольку могут на расстоянии дать понимание, к примеру, слов, принадлежащих к схожему кластеру (“яблоки”, “апельсины”) или означающих схожие вещи.

Ключевые моменты

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